ЕГЭ по информатике: 2018 и далее презентация

С. Кравцов:
«Планируем через два года ввести полностью информатику на компьютерах». 21.02.2018

Укажите наименьшее число, двоичная запись которого содержит ровно три значащих нуля и три единицы. Ответ запишите в десятичной системе счисления

1000112 = 35

12

102

1 2 F 0

11112

511?

511 = 512 - 1
= 10000000002 - 1 = 1111111112
Ответ: 9

519?

519 = 512 + 7
512 = 10000000002 7 = 1112
плюс три единицы: 4

1000102 = 34 ≤ N ≤ 1111102 = 62
1xxx10 ⇒ делится на 2
1xxx10 ⇒ не делится на 4

Даны две логические функции F и G от 5 одинаковых переменных. В их таблицах истинности 5 одинаковых строк, причём в 3 из них обе функции равны 1. При скольких комбинациях переменных
функция F∙G равна 0 (равна 1)
функция F+G равна 0 (равна 1)

x

y

w

или

z

x

z

y

w

x

z

y

или

w

x

z

y

Ответ: zyx

1

0

0

x

z

y

Ответ: zyx

Ответ: zyx

c

a

b

x

z

y

Ответ: zyx

x

z

y

x

z

y

Ответ: zxy

1

0

1

0

x

z

y

Ответ: zxy

0

0

1

1

0

1

0

x

z

y

w = 0: F = (y ≡ x) + (y → 0) = 0.
y = 1, x = ¬ y = 0, z = {1, 0}

w = 1: F = (1 ≡ x) + (1 → z) = 0.
x = 0, z = 0, y = {1, 0}

убираем данные про отцов

27

26

19

27

21

30

28

5

Д

010

4: 1xx
2: 01x
1: 001

5 согласных букв ⇒ ≥ 3 бита

свободны: 000

4 бита

000x

000xx

5 бит

000xxx

6 бит

1

2

4

8

чётность восстановлена!

Должны получить чётное = 126 или 128 или …

После div 2 должна сохраниться чётность!

126 / 2 = 63 = 1111112 : – 6 единиц, чётность

Должны получить чётное = 138, 140, 142, …

После div 2 должна сохраниться чётность!

138 / 2 = 69 = 10001012 : – 3 единицы, нечётность

140 / 2 = 70 = 10001102 : – 3 единицы, нечётность

142 / 2 = 71 = 10001112 : – 4 единицы, чётность

П**** 24 = 16 слов

Ответ: 16· 5 = 80.

# * * * #

Ответ: 5 · 6 · 6 · 6 · 5 = 5400.

5

5

Ответ: 113.

не А!

Ответ: 625 – 256 – 256 = 113

*.*.112.*

*.*.64.0

112 = 011100002

64 = 010000002

маска: 110000002 = 192

192

не забываем про старшие единицы!

*.*.208.*

*.*.192.0

208 = 110100002

192 = 110000002

маска: 111000002

192

маска: 110000002

IP: 11000000.00000000.00001100

маска: . .

сеть: 11000000.00000000.00000000

11

******.********.****

0000

18 свободных битов

Ответ: 19

наименьшее N > 1
наибольшее N
все возможные N
сумма всех N

N = общий делитель(25,10)

Каков результат обработки строки 88888…8 ?

68

888888888…8

2

2

2

8

68 - 8·8 = 4

8888 → 28

2: ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (888)
ТО заменить (888, 2)
ИНАЧЕ заменить (222, 8)

8888888888888888888

2228888888888

⇒ 88888888888

8888888888888888888

⇒ 2222228

10N = 100…0

N

10N-1 = 99…9

N

2N = 100…02

N

2N-1 = 11…1

N

3N = 100…03

N

3N-1 = 22…2

N

= 11…100…02

N-M

M

1

4399

1 + 4399 = 4400

4400

8148 = 2444
4123 = 2246
2654
17 = 32 – 15
= 25 – 24 + 20

2654 + 2444 – 2246 – 25 + 24 – 20

1

198

197

241

2246 – 25 + 24 – 20

4

1 + 197 + 241 + 4 = 443

443

8148 = 2444
4123 = 2246
2654
17 = 16 + 1
= 24 + 20

2654 + 2444 – 2246 – 24 – 20

1

444

1 + 444 – 2 = 443

443

2444 – 2246 – 24 – 20

– 2

9118 = 3236
27 = 33

3236 + 3123 – 33

1

NА | B = NA + NB – NA & B

NA = 450 – 260 + 50 = 240

240

A & B

B

A

NA & B = 22 + 40 + 24 – 12 – 66 =

8

Правило включений и исключений для 3-х областей:

тождественно истинно, то есть равно 1 при любом значении переменной х.

20

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {4, 8, 12, 116}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))

Σ = 24

(x & 49 ≠ 0) → ((x & 33 = 0) → (x & A ≠ 0))

(x & 49 ≠ 0) → ((x & 33 = 0) → (x & A ≠ 0))

номер бита 5 4 3 2 1 0
49 = 110001
X = abcdef
X & 49 = ab000f

x & 49

x & 49 = 0

⇒ все биты {5, 4, 0} нулевые

x & 49 ≠ 0

⇒ среди битов {5, 4, 0} есть ненулевые

(x & 49 ≠ 0) → ((x & 33 = 0) → (x & A ≠ 0))

x & 33 = 0

⇒ все биты {5, 0} нулевые

P: x & 49 ≠ 0

⇒ среди битов {5, 4, 0} есть ненулевые

номер бита 5 4 3 2 1 0
33 = 100001

Amin = 24 = 16

(x & A ≠ 0) → ((x & 20 = 0) → (x & 5 ≠ 0))

⇒ все биты {2, 0} нулевые

x & 20 = 0

⇒ все биты {4, 2} нулевые

Amax = 24 + 22 + 20 = 21

истинно при любом натуральном х. Определите наибольшее возможное значение A.

(x & A ≠ 0) → ((x & 20 = 0) → (x & 5 ≠ 0))

Они обнулят биты числа при &!

9 ⋅ 9 ≤ A ⇒ Amin = 81

((x ≤ 9) → (x⋅x ≤ A)) ∧ ((y⋅y ≤ A) → (y ≤ 9))

Решение:

1) при x ≤ 9 нужно обеспечить x⋅x ≤ A

2) при y > 9 нужно обеспечить A < y⋅y (избежать 1 → 0)

A < 10 ⋅ 10 ⇒ Amax = 99

( (x ∈ A) → (x2 ≤ 100) ) ∧ ( (x2 ≤ 64) → (x ∈ A) )

Решение:

1) при x ∈ A нужно обеспечить x2 ≤ 100

2) при x2 ≤ 64 нужно обеспечить x ∈ A

| x | ≤ 10 ⇒ A ∈ [-10; 10]

| x | ≤ 8 ⇒ [-8; 8] ∈ A

| Amax | = 20

| Amin | = 16

перестановка пары при сортировке пузырьком

1) 9 6 7 2 1 5 0 3 4 8

2) 9 7 6 2 1 5 0 3 4 8

3) 9 7 6 2 5 1 0 3 4 8

4) 9 7 6 2 5 1 3 0 4 8

5) 9 7 6 2 5 1 3 4 0 8

6) 9 7 6 2 5 1 3 4 8 0

с = 6

перестановка пары

4 7 3 8 5 0 1 2 9 6

4 7 3 8 5 0 1 2 9 6

3 7 4 8 5 0 1 2 9 6

с = 2

s:=A[0]-A[1]+A[1]-A[2]+A[2]-...
+A[7]-A[8]+A[8]-A[9]+A[9]-A[10]

max = 999 – 100 = 899

s:=A[0]-A[2]+A[1]-A[3]+A[2]-...
+A[6]-A[8]+A[7]-A[9]+A[8]-A[10]

max = 999 + 999 – 100 – 100 = 1798

1798

a := 0;
b := 10;
readln(x);
while x > 0 do begin
y := x mod 10;
x := x div 10;
if y > a then a := y;
if y < b then b := y;
end;
writeln(a);
writeln(b);

33336

{ максимальная цифра }
{ минимальная цифра }

var x, L, M: integer;
begin
readln(x);
L := x; M := 65;
if L mod 2 = 0 then
M := 52;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

x нечётное: НОД(x,65) = 26

x чётное: НОД(x,52) = 26

x делится на 26,
не делится на 52!

104

НОД(104,52) = 52

function f(n: longint): longint;
begin
f:= n*(n-1)+10
end;
…
readln(k);
i:= 0;
while f(i) < k do
i:= i + 1;
writeln(i);

36

Останов: f(i) >= k

31 … 40

10

8

23 … 30

function f(n: longint): longint;
begin
f:= n*(n-1)+10
end;
…
readln(k);
i:= 0;
while f(i) < k do
i:= i + 1;
writeln(i);

Останов:
f(i-1) < k <= f(i)

31 … 40

(i-1)*(i-2)+10 < k <= i*(i-1)+10

i2-3i+12 < k <= i2-i+10

i=6: 30 < k <= 40

def f(n):
return n*n*n
def g(n):
return 2*n+3
k = int(input())
i = 1
while f(i) < g(k):
i+=1
print (i)

Останов:
f(i-1) < g(k) <= f(i)

3 … 12

(i-1)3 < 2k+3 <= i3

k=10: (i-1)3 < 23 <= i3

i=3

8 < 2k+3 <= 27

Рекуррентная формула:

новый старт

сюда нельзя

Рекуррентная формула:

readln(x);
c:= 0;
while x > 0 do begin
c:= c + x mod 2;
x:= x div 10
end;
writeln(c)

Только для x=1

неверное начальное значение
неверное условие цикла
неверное изменение переменных
неверный вывод

readln(N);
maxDigit := N mod 10;
while N > 0 do begin
digit := N mod 10;
if digit mod 3 = 0 then
if digit > maxDigit then
maxDigit := digit;
N := N div 10;
end;
if maxDigit = 0 then writeln('NO')
else writeln(maxDigit);

последняя цифра делится на 3
находим максимум

-1

-1

выигрышная стратегия есть у Пети
ему нужно написать букву А
при этой стратегии возможна одна партия
она закончится словом АБВГДАБВГДХ

выигрышная стратегия есть у Пети
ему нужно написать букву Т
при этой стратегии возможна одна партия
она закончится словом ТРИТРИ…ТРИ

в слове ДГВБАДГВБА поставить на первое место А, например, поменять местами первую и последнюю буквы: {АБВГДАБВГДХ, АГВБАДГВБД}
Ване нужно написать букву Г
при этой стратегии возможна одна партия
она закончится словом АГВБАДГВБД

2
1
2

2

К Р О Н А
К Р О Ш К А
К Р О К О Д И Л И Щ Е

1
2
1

2

выиграет

выбирает

12, 14
21, 22, 24
41, 42, 44

Окончание партии: цепочка заканчивается на X, и нет фишек, начинающихся с X.

меньше всего фишек

Идея – А. Сидоров

ничего не даёт

Ваня не может применить 44!

Первый ход Вани – 22.

ИЛИ…?

12, 14
21, 22, 24
41, 42, 44

12, 14, 21, 22, 24, 41, 42, 44

Граф игры:

1) выставляется 4 фишки, например:

2) выставляется 6 фишек, например:

12–24–41–14–42–21

12–21–14–41

Задача А (2 балла). O(N2) по времени, O(N) по памяти.

Задача Б (3 балла). O(N) по времени, O(N) по памяти.

Задача Б (4 балла). O(N) по времени, O(1) по памяти.

var N: integer;
a: array[1..10000] of integer;
i, j, max: integer;
begin
readln(N);
for i:=1 to N do read(a[i]);
max:= -1;
for i:= 9 to N do
for j:= 1 to i-8 do
if (a[j]*a[i] > max) then
max := a[j]*a[i];
writeln(max)
end.

i

i-8

m

a[i]

накапливать!

max:= 0;
m:= 0;
for i:= 9 to N do begin
if a[i-8] > m then m := a[i-8];
if m*a[i] > max then max := m*a[i];
end;

i-8

x

var a: array[1..8] of integer;

for i:=1 to 8 do read(a[i]);

Начальное заполнение массива:

Продвижение:

for i:=1 to 7 do
a[i]:=a[i+1];
a[8]:= x;

i

const d = 8; { сдвиг }
... { уже прочитали первые d штук }
max:= 0;
m:= 0;
for i:=d+1 to N do begin
read(x);
if a[1] > m then m:= a[1];
if m*x > max then max:= m*x;
for j:=1 to d-1 do
a[j]:= a[j+1];
a[d]:= x;
end;

a[1]

x

for i:=0 to d-1 do read(a[i]);

for i:=d to N-1 do begin
read(x);
k:= i mod d;
if a[k] > m then m := a[k];
if m*x > max then max := m*x;
a[k]:=x;
end;

9

10

11

k

12

x

чётное ← чётное * любое
чётное ← любое * чётное

x

максимальное чётное

получено нечётное

получено чётное

а делится на 26, b – любое
a делится на 13, b делится на 2
а делится на 2, b делится на 13

Вычисляем:

n26 – количество делящихся на 26
n13 – количество делящихся на 13, но не на 26
n2 – количество делящихся на 2, но не на 26