Variant_18052020_разбор

Формат документа: pdf
Размер документа: 0.87 Мб





Прямая ссылка будет доступна
примерно через: 45 сек.



  • Сообщить о нарушении / Abuse
    Все документы на сайте взяты из открытых источников, которые размещаются пользователями. Приносим свои глубочайшие извинения, если Ваш документ был опубликован без Вашего на то согласия.

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 1 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Единый государственный экзамен
по ИНФОРМАТИКЕ и ИКТ

Инструкция по uiheg_gbxjZ[hlu
Экзаменационная работа состоит из двух частей, dexqZxsbo в себя
27 заданий. Часть 1 содержит 23 задания с кратким от_lhf , ч асть 2
содержит 4 задания с разzjgmlufhlето м.
На uiheg_gb_ экзаменационной работы по информатике и ИКТ
отh^blky3 часа 55 минут (235 минут).
От_lu к заданиям 1 –23 записыZxlky  b^_ числа,
последоZl_evghklb[md или цифр. Ответы запишите  поле от_lZ тексте
работы, а затем перенесите [ew нк от_lh № 1.


Задания 24 –27 требуют разzjgmlh]h от_lZ В бланке от_lh № 2
укажите номер задания и запишите его полное решение .
Все бланки ЕГЭ заполняются яркими чёрными чернилами.
До пускается использоZgb_]_e_ой или капиллярной ручки .
При в ыполн ении заданий можно пользоZlvkyq_jgh\bdhf Записи
q_jghике, а также l_dkl_dhgljhevguobaf_jbl_evguofZl_jbZeh\
не учитыZxlkyijbhp_gbании работы.
Баллы, полученные Вами за uiheg_g ные задания, суммируются.
Постарайтесь uihegblvdZdfh`gh[h льше заданий и набрать наибольшее
количестh[Zeeh.
После за_jr_gby работы про_jvl_ что от_l на каждое задание в
бланках от_lh №1 и №2 записан под праbevgufghf_jhf.

Желаем успеха!












В экзаменационных заданиях используются следующие согл ашения.

1. Обозначения для логических сyahd hi_jZpbc :
a) отрицание (ин_jkbyeh]bq_kdh_G? h[hagZqZ_lky¬ (например, ¬А);
b) конъюнкция (логическое умножение, логическое И) обозначается / \
(например, А / \ В) либо & (например, А & В);
c) дизъюнкция (логическое сл ожение, логическое ИЛИ) о бозначается \/
(например, А \/ В) либо | (например, А | В);
d) следоZgb_ bfiebdZpby h[hagZqZ_lky: gZijbf_j::< ;
e) тождестhh[hagZqZ_lkyA (например, A ≡ B). Выражение A ≡ B истинно
тогда и только тогда, когда значения A и B соiадают (либо они оба
истинны, либо они оба ложны);
f) симhe 1 используется для обозначения истины (истинного
ukdZauания); симhe 0 – для обозначения лжи (ложного
ukdw зыZgby .

2. ДZ логических ujZ`_gby содержащих переменные, назыZxlky
раghkbevgufb (эк виZe_glgufb  если значения этих ujZ`_gbc
соiZ^Zxlijbex[uoagZq_gbyoi_j еменных. Так, ujZ`_gby::<b :
\/ В раghkbevgu а А \/ В и А / \ В нераghkbevgu (зна чения ujZ`_gbc
разные, например, при А = 1, В = 0).

3. Приоритеты логических операций: ин _jkby (отрицание), конъюнкция
(ло гическое умножение), дизъюнкция (логическое сложение), импликация
(следоZgb_ lh`^_klо. Таким образом, ¬А / \ В \/ С / \ D означает т о же, что
и ((¬А) / \ В) \/ (С / \ D).
Возможна запись А /\ В /\ С f_klh (А / \ В) /\ С. То же относится и к
дизъюнкции: hafh`gZaZibkv: \/ В \/ С f_klh : \/ В) \/ С.

4. Обозначения Мбайт и Кбайт используются  традиционном для
информатики смысле – как обо значения единиц измерения, чьё соотношение
с единицей «байт» ujZ`Z_lkykl_i_gvx^\hcdb.

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 2 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Часть 1
От_lZfb к заданиям 1 –23 яeyxlky число, последоZl_evghklv букв
или цифр, которые следует записать ;E:GDHL<?LH<kijZа от
номера соот_lklующего задания, начиная с перhc клеточки, без
пробело запятых и других дополнительных симh лов . Каждый симhe
пишите hl^_evghcde_lhqd_ соот_lklии с приведённым и [eZgd_
образцами.

Найдите максимальное шестнадцатеричное число, соот_lkl\mxs__
следующим услоbyf:
- qbke_g_lgme_c,
- разряды располагаются \hajZklZxs_fihjy^d_( наприм ер, 12 34),
- ^\hbqghcaZibkb^Zggh]hqbkeZ_^bgbp .
В качест_ от_lZ приведите найденное шестнадцатеричное число.
ОсноZgb_kbkl_fukqbke_gbymdZauать не нужно.

Решение :
Так как нам нужно максимальное число, необходимо задействоZlv
максимальное чис ло разрядо (чем длиннее значащая часть числа, тем оно
бо льше).
Поэтому  двоичном предстаe_gbb каждого шестнадцатеричного разряда
нужно использоZlvfbgbfZevgh_dhebq_klо единиц.
Разрядоkh^ghc_^bgbp_cсего 4 – 1 (0001), 2 (0010), 4 (0100), 8 (1000) .
Значит  искомом числе будут шестнадцатеричные разряды, двоичная
запись которых содержит большее количестh_^bgbp.
Разряды с дmfy_^bgbpZfb – 3 (0011), 5 (0101), 6 (0110), 9 (1001), A (1010),
C (1100).
Разряды с тремя единицами – 7 (0111), B (1011), D (1101), E (1110).

Чтоб k_]h_^bgbp[ueh возможны два случая – 4 по 1 и 1 по 3, 3 по 1 и 2
по 2.

Для перh]hkemqZyjZkklZ\ey_fjZajy^Z порядке hajZklZgbyb
конец дописыZ_ffZdkbfZevgucjZajy^klj_fy_^bgbpZfb E.

Для второго случая u писыZ_f три максимал ьные значения с одной
единицей: 248,  конец дописыZ_f два максимальных значения с двумя
единицами AC .

Выбираем максимальное из полученных чисел.

Ответ: ___ 248 AC _______________________.
Вася успел заполнить лишь фрагмент таблицы и стинности для ujZ`_gby
((x → y) \/ ¬ (z → w))/\((w → ¬x) \/ (¬y → z)), даже не указа, какому столбцу
таблицы соот_lklует каждая из переменных w, x, y, z .
? ? ? ? ((x → y) \/ ¬ (z → w))/\((w → ¬x) \/ (¬y → z))
0 0 0 0
0 1 0
0 0 1 0
Определите, к акому столбцу таблицы соот_lkl\m_ldZ`^Zybai_j_f_gguo
w, x, y, z .
В от_l_ напишите букu w, x, y, z  том порядке,  котором идут
соот_lkl\mxsb_ им столбцы (сначала букZ соот_lkl\mxsZy перhfm
столбцу; затем букZ соответствующая lhjhfm столбцу, и т.д.). Букu 
от_l_ пишите подряд, никаких разделителей между букZfb ставить не
нужно.
Пример . Функция задана ujZ`_gb_f ¬x \/ y , заbkysbf от двух
переменных,
а фрагмент таблицы имеет следующий вид.
¬x \/ y
0 1 0
В этом случае перhfmklhe[pmkhh т_lklует переме нная y, а lhjhfm
столбцу – переменная x. В от_l_ke_^m_lgZibkZlv yx.

Решение :
Заметим, одно из подвыражений ((x→y) \/ ¬(z→ w)) и ((w→¬ x) \/ (¬y→ z))
должно быть ложным
Найдем наборы, при которых одно из подвыражений ложно .
((x→y) \/ ¬(z→w)) ((w→¬ x) \/ (¬y→z))
x y z w x y z w
1 0 0 0 1 0 0 1
1 0 0 1
1 0 1 1
Имеем k_]hljbgZ[hjZ gZ[hj^m[ebjm_lky .
В перhckljhd_lZ[ebpug_fh`_l[ulv[hevr_h^ghc_^bgbpu
следоZl_evghihke_^gbcklhe[_p – х. Д__^bgbpufh`_l[ul ь только 
столбце w, следоZl_evghwlhklhe[_p. Три единицы может быть только
hторой строке, следоZl_evghklhe[_p – z.

Ответ: ___ yzwx _____________________.
1
2

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 3 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

На рисунке слеZ изображена схема дорог N -ского района. При_^_gu
длины дорог между п унктами. Так как таблицу и гр аф заполняли
незаbkbfh наименоZgb_ _jrbg графа никак не заbkyl от номеров
пункто  таблице . Найдите номера пункто G и H. В качест_ от_lZ
запишите найденные номера ihjy^d_озрастания без разделителей .

Номер пункт а
1 2 3 4 5 6 7 8
Номер пункта
1 * * * *
2 * *
3 * * * *
4 * *
5 * *
6 * * * *
7 * *
8 * *

Решение :
Найдем _jrbgm А. Из нее дороги _^ml только  _jrbgu где по четыре
исходящих дороги. Следов ательно _jrbgZ: – пункт 2. Значит _jrbgu<
и С это _jrbgub ^eygZkg_ijbgpbibZevgh однозначное определение
\b^m симметричности графа). Найдем номера в ершин D, E, F – 3, 4 и 5. В
них _^ml^hjh]bbaimgdlh 1 и 6.

СледоZl_evghbkdhfu_ершины имеют номера 7 и 8.










От_l_ ___ ____ 78 _____________________.
Ниже предстаe_gu дZ фрагмента таблиц из базы данных о жителях
микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и
об одном из его родителей. Информация представлена з начением поля ID в
соот_lkl\mxs_ckljhd_lZ[ebpu Сколько детей родилось, после того, как
их бабушке или дедушке исполнилось 60 лет.
Таблица 1 Таблица 2
ID Фамилия_И.О. Пол Год_рождения ID_ Родителя ID_ Ребёнка
11 Отменина Н.Е. Ж 1932 70 23
22 Экзам енов О.Е. М 1997 70 22
23 Карантенко А.А. Ж 1987 70 50
27 Мешаллкин Е.А. М 1973 11 27
30 А]mklhа А.А. Ж 1940 65 27
44 Июлькин А.И. М 1935 30 70
48 Непонятко Д.Д Ж 1960 11 48
49 Паника И.И. Ж 1991 65 48
50 Подготоbg П.П. М 1989 68 66
65 Поступенко К.Т. М 1930 44 70
66 Неслужбин К.Л. Ж 1994 30 68
68 Родина Л.К. М 1972 27 23
70 Косоw Г.Г. Ж 1961 27 22
… … … … 27 50
48 49
… …
Решение :
Найдем людей, которые яeyxlky одноj_f_ggh детьми и родителями,
чтобы найти бабушек и дедушек. В столбце родителей и детей одноj_f_ggh
есть 68, 70, 27, 48 . Они имеют одинакоuojh^bl_e_cke_^hательно только
их дети могут быть двоюродными братьями или сестрами.
68, 70 27, 48
Дети Род -и Разница Дети Род -и Разница
66
30
1994 -1940=54 23
11
1987 -1932=55
23 1987 -1940=47 22 1997 -1932= 65
22 1997 -1940=57 50 1989 -1932= 57
50 1989 -1940=49 49 1991 -1932= 59
66
44
1994 -1935=59 23
65
1987 -1930= 57
23 1987 -1935=53 22 1997 -1930= 67
22 1997 -1935= 63 50 1989 -1930= 59
50 1989 -1935=53 49 1991 -1930= 61
Итого у 22 и 50 на момент рождения бабушке или дедушке было больше 60.

Ответ: ________ 2__________________.
3 4

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 4 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

По каналу сyab передаются сообщения, содержащие только шесть бук:
А, В, Г, У, С, Т; для передачи используется двоичный код,
удоe_l\hjyxsbc услов ию Фа но.
Букu Т, У, С, А имеют коды 10, 000, 11, 001 соот_lkl\_ggh.
Укажите наименьшую hafh`gmx длину закодироZgghc
последоZl_evghklb^eykehа СУСТАВ .

Примечание . Услоb_NZgh означает, что никакое кодовое слоhg_yляется
началом другого кодоh]h слоZ Это обеспечиZ_l hafh`ghklv
однозначной расшифроdbaZdh^bjhанных сообщений.

Решение :
Заметим, что ноu_ кодовые слоZ могут начинаться только с 01 (k_
остальные начальные последоZl_evghklbm`_bkihevahаны) .
По услоbx задачи необходимо зако дироZlv две букu В и Г.
Следоw тельно коды для этих бук[m^mlb.

Значит наименьшая длина закодироZgghc последоZl_evghklb для слоZ
СУСТАВ = 2 + 3 + 2 + 2 + 3 + 3 = 15


Ответ: _________ 15_______________.
Исполнитель ХочуЛето изменяет \_^_g ное число по заданной
пользоZl_e_f программе.
У исполнителя две команды:
1) Прибавить 3,
2) Умножить на 1.5.
ПерZydhfZg^ZmеличZ_lqbkehgZторая – у_ebqbает число ihelhjZ
раза. Если число нечетное, результатом lhjhc команды будет целая часть
числ а, полученного при умножении. Например, результатом применения
команды 2 к числу 5 будет число 7. Програм ма представляет
последоZl_evghklvaZibkZgguodhfZg^
Например, программа 1121 – это программа
прибаblv3 ,
прибаblv3 ,
умножить на 1.5 ,
прибаblv3 ,
которая преобразует числ о 7 в число 22.

Запишите порядок команд  программе, которая преобразует число 10 
число 40 и содержит не более 4 команд. УказыZcl_ebrvghf_jZdhfZg^.

Решение :
Начнем решение от обратного.
В 40 можно попасть из чисел 37 и 27 ,
В 27 – из 24 и 18,
В 18 – из 15 и 12,
В 12 – из 8 и 9 (значит нашапрограмма не должна проходить через 12),
В 15 – из 12 и 10.

Мы попали  10, следоZl_evgh нашли программу. Запишем примененные
операции h[jZlghfihjy^d_.


Ответ: _________ 2122 ________ ________.

5 6

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 5 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Дан фрагмент электронной таблицы. Какое значение должно стоять yq_cd_
А1, чтобы построенная по значениям ячеек A2:C2 диаграмма
соот_lkl\hала рисунку? Из_klgh что k_ ячейки  рассматриZ_fhf
диапазоне положительные .
A B C

1 8 5
2 =A1+B1 –6 =(2*A1+C1 –1)/2 =(A1+2)*(A1 -3)


Решение :
Подставим из_klgu_agZq_gby
=A1+ 8–6 =(2*A1+ 5–1)/2 =(A1+2)*(A1 -3)
Упростим полученные ujZ`_gby
=A1+ 2 =A1+ 2 =(A1+2)*(A1 -3)
Имеем, что при любом значений А1 значения yq_cdZo:b< одинакоu_
Сле доZl_evghg_h бходимо исследоZlvnhjfmem ячейке С2.

(A1+2)*( A1-3) = A1+ 2
(A1+2)*( A1-4) = 0

А1 = -2 или А1 = 4.

По услоbx значение должно получиться положительное . При А1 = -2,
получаем три нуля. При А1 = 4 получаем три 6.

Ответ: ______ 4___________ ________.

Запишите число, которое будет напечатано  результате uiheg_gby
следующей программы. Для Вашего удобстZ программа представлена на
нескольких языках программироZgby
C++ Паскаль
#include
using namespace std;
int main() {
int s = 611 , n = 476 ;
while ( s – n > 0 ) {
s = s - 21 ;
n = n - 16 ;
}
cout << n << endl;
return 0;
}
var s, n: integer;
begin
s := 611 ;
n := 476 ;
while s - n > 0 do
begin
s := s - 21 ;
n := n - 16
end;
writeln( n)
end.
Python Бейсик
s = 611
n = 476
while s – n > 0:
s = s - 21
n = n - 16
print( n)
DIM S, N AS INTEGER
S = 611
N = 476
WHILE S – N > 0
S = S - 21
N = N - 16
WEND
PRINT N

Решение :
Перед uiheg_gb_fpbdeZagZq_gb_ыражение S – N = 135.
На каждой следующей итерации будет происходит ь следующее изменение:
(S - 21) – (N - 16) = S – N – 5.
Значит после каждой итерации значение ujZ`_gby S – N уменьшается на 5.
Найдем количестhbl_jZpbcg_h[oh^bfh_^eyыхода из цикла.
135:5 = 27.

После 27 итерации значение S – N раgh.

Вычислим ко нечное знач ение переменное N.
476 - 27*16 = 476 – 432 = 44

Ответ: _______ 44__________________.




7 8

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 6 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

АlhfZlbq_kdZy камера произh^bl растроu_ изображения размером
1280х19 20 пикселей. Для кодироZgbypета каждого пикселя используется
одинакоh_ количест h бит, коды пикселей записыZxlky  файл один за
другим без промежуткоH[t_fnZceZkbah[jZ`_gb_fg_fh`_lij_ышать
1500 Кбайт без учета размера заголоdZ файла. Какое максимальное
количестhpетоfh^ghbkihevahать iZeblj_?

Решение :
В перmxhq_j едь необходим о определ ить предельное количестh[blh на
один пиксель.
1500 ∗213
1280 ∗1920 = 1500 ∗213
27∗10 ∗26∗30 = 5

Значит на один пиксель можно u^_eblvg_[he__[bl.
5 бит могут хранить 2 5 комбинаций. Это число и будет от_lhfgZaZ^Zqm.


Ответ: _______ 32___________________.

Стасик uibkuает k_iylbkbfольные комбинации, состаe_ggu_ из букв
Ш, К, О, Л, А. При этом упорядочиZyboihZenZ\blm.
Вот начало списка:
1. ААААА
2. ААААК
3. ААААЛ
4. ААААО
5. ААААШ

Определите, сколько слоohly[ukh^gh й гласной напишет Стасик.

Решение :
Общее количестhkeh равно 55 = 3125.
Количестhkeh БЕЗ гласных раgh 35 = 243.

Значит количестhkeh хотя бы с одной гласной раgh – 243 = 2882.

Ответ: _______ 2882 ____________________.
9 10

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 7 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Дан рекурсиgucZe]hj итм.
C++ Паскаль
void F(int n){
if (n > 2){
F(n - 1);
std::cout << "*" ;
G(n);
}
}
void G(int n){
if (n > 5) F(n / 2);
std::cout << "*" ;
}
procedure F(n: integer);
begin
if n > 2 then begin
F( n - 1);
write( "*" );
G(n);
en d;
end;

procedure G(n: integer);
begin
if n > 5 then F(n div 2);
write("*");
end;
Python Бейсик
def F(n):
if n > 2:
F(n - 1)
print("*", end='')
G(n)
def G(n):
if n > 5:
F(n // 2)
print("*", end='')
SUB F( N)
IF N > 2 THEN
F( N - 1)
PRINT "*" ,
G(N)
END IF
END SUB
SUB G(N)
IF N > 5 THEN
F( N \ 2)
END IF
PRINT "*" ,
END SUB
Сколько симheh «зza^hqdZ[m^_lgZi_qZlZghgZwdjZg_ijbыполнении
G(13) .

Решение :
Построим дереhызоhy

Отв ет: ______ 11________________.
11

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 8 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

В терминологии сетей TCP/IP маской сети назыZ_lky двоичное число,
определяющее, какая часть IP -адреса узла сети относится к адресу сети, а
какая – к адресу самого узла wlhck_lbH[uqghfZkdZaZibkuается по тем
же праbe ам, что и IP -адрес, – иде четырёх байтоijbqzfdZ`^uc[Zcl
записыZ_lky виде десятичного чис ла. При этом fZkd_kgZqZew (klZjrbo
разрядах) стоят единицы, а затем с некоторого разряда – нули. В рамках
такой сети u^_e_gh дZ служебных адреса – адр ес сети и
широко_sZl_evguc адрес – k_ нули или k_ еди ницы  адресе узла сети.
Данные адреса запр ещено использоZlv качест_ IP-адресоmaeh сети.
Адрес сети получается j_amevlZl_ijbf_g_gbyihjZajy^ghcdhgtxgdpbb к
заданному IP -адресу узла и маске.
Например, если IP -адрес узла ра_g 231.32.255.131, а маска раgw
255.255.240.0, то адрес сети ра_g.

ДZ узла с IP -адрес ами 201.44.240.33 и 201.44.240.107 находятся  одной
сети . Сколько hafh`guo ZjbZglh маски допускает такой случай, если
из_klghqlh двоичном представлении адреса сети не менее 5 единиц ?

Решение :
Запишем заданные IP-адреса один под другим и определим биты, которые
должны быть равны 1 и 0.
Нули должны быть h[eZklb]^_ IP-адреса отличаются, ijhlbном случае
имеем р азные сети.
Так как  адресе сети должно быть не менее 5, минимальное количестh
единиц определяем до пятой единицы  IP-адресах.
На остальных позициях любой набор бит fZkd_g_ijhlbоречит услоbx.

IP адрес 1 11 001001 00101100 11110000 00100001
IP адр ес 2 11001001 00101100 11110000 01101011
Маска сети 11111111 111 ххххх хххххххх х 0000000

Не определено 14 бит, следоZl_evghозможных значений маски может
быть 15.

00…000
00…001
….
11…111
Ответ: ____ ___15___________________.
При регистрации dhfivxl ерной системе каждому пол ьзоZl_exыдаётся
пароль, состоящий из 11 симheh и содержащий только симheu из
11 -симhevgh]h набора: Х, О, Ч, У, Е, Г, Э, В, И, Ю, Л. В базе данных для
хранения с_^_gbc о каждом пользоZl_e_ от_^_gh одинакоh_ и
минимально в озможное целое число байт . При этом используют
посимhevgh_ кодироZgb_ паролей, k_ симheu кодируют одинакоuf и
минимально hafh`guf количестhf бит. Кроме собст_ggh пароля, для
каждого пользоZl_ey в системе хранятся IP-адрес (4 Байта) и
дополнительны е с_^_gby. На хранение дополнительных с_^_gbchlеден о
одинаков ое для каждого пользоZl_ey целое количестh[Zcl .
Для хранения с_^_gbch 30 пользоZl_eyoihlj_[hалось 840 байт.
Сколько байт u^_e_gh для хранение дополнительных данных о
пользоZl_e| ? В от_l_aZibrbl_lhevdhp_eh_qbkeh – количестh байт .

Решение :
Так как алфавит содержит 11 симheh, то на кодироZgb_h^gh]hkbfола
необходимо 4 бита ( 23 < 11 ≤ 24)
На один пароль требуется 11*4 = 44 бита.

На одного пользоZl_eyыделяется 840/30 = 2 8 Байт

Значит на доп.информацию u^_ey_lkyg_[he__ – 4 ( IP)– 5.5 (пароль) =
18.5 Байт.

По услоbxqbkeh;Zclp_eh_

Ответ: _________ 18________________.
13 12

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 9 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Исполнитель Редактор получает на oh^kljhdm симheh и преобразоuает
её. Редактор может ui олнять д_ команды ,  обеих командах v и w
обозначают цепочки симheh.
А) заменить ( v, w ).
Эта команда заменяет в строке перh_ke_а oh`^_gb_p_ihqdbYgZp_ihqdm
w.
Например, uiheg_gb_dhfZg^u
заменить (ABC , D)
преобразует строку DCABCD kljhdm DCDD .
Если  строке нет oh`^_gbc цепочки v, то uiheg_gb_ команды
заменить (v, w) не меняет эту строку.
Б) нашлось ( v).
Эта команда про_jy_l klj_qZ_lky ли цепочка v в строке исполнителя
Редактор. Если она klj_qZ_lky то команда haращает логическое значени е
«истина»,  протиghf случае haращает значение «ложь». Строка
исполнителя при этом не изменяется.
Цикл
ПОКА услоb|
последоZl_evghklvdhfZg^
КОНЕЦ ПОКА
uihegy_lkyihdZmkeh\b_bklb нно.
В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ Е СЛИ
uihegy_lkydhfZg^Z _kebmkehие истинно).
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
uihegy_lkydhfZg^Z _kebmkehие истинно) или команда2 (если услоb|
ложно).
В от_l на задачу при_^bl_ строку, полученную пос ле преобразоZgby
строки, состоящей из 107 букO .

НАЧАЛО
ПОКА нашлось( XXX ) или нашлось( ZYX ) или нашлось( ZXX )
заменить( XXX , ZZ )
заменить( ZYX , X)
заменить( ZXX , Y)
КОНЕЦ ПОКА
КОНЕЦ

Решение :
Рассмотрим, как алгоритм преобразует строку на стр оке меньшей длины.

ХХХХХХХХХХХХХХ
1 итерация
ZZXXXXXXXXXXX
ZYXXXXXXXXX
2 итерация
ZYZZXXXXXX
ZYZYXXXX
Заметим, что на каждой итерации 5 букOaZf_gyxlkygZkljhdm ZY .

Значит после перh]h крупного шага алгоритм преобразует начальную
строк у ihke_^hательность из 21 ZY и 2 Х.

ZYZYZYZYZYXX
1 итерация
ZYZYZYZYXX
2 итерация
ZYZYZYXX

Получается, что k_ последоZl_evghklv ZY после окончания uiheg_gby
цикла исчезнут.


Ответ: ______ XX __ ________________.
14

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 10 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

На рисунке представлена схема дорог, сyauающих города
A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только 
одном направлении, указанном стрелкой.
Сколько сущестm_lfZjrjmlhy из А  H, которые проходят через пунк т С
или пункт L?

Решение :
Зачеркнем k_ дороги, при движении по кото рым мы не проходим через
обозначенные пункты. И решим задачу обычным алгоритмом.


Ответ: _______ 14___________________.
Значение ujZ`_gby записали  семеричной системе счисления . Ск олько
нулей lZdhc записи?

52∙725 +62∙736 −42∙93


Решение :
25 = 3*7 + 4
36 = 5*7 + 1
52∙725 +62∙736 = 5∙737 +736 +3∙726 +4∙725

42∙93= 11664 = 46002 7

Выполним uqblZgb_ семеричной системе счисления.
51000000000 34 00…000000
46002
51 000000000 3366…62 0664

Ответ: _ ________ 10________________.


15 16

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 11 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

В языке запросоihbkdhого сер_jZ^eyh[hagZq_gbyeh]bq_kdhc операции
«ИЛИ» используется симhe «|», а для обозначения логической операции
«И» – симhe .
В таблице при| дены запросы и колич естh найденных по ним страниц
некоторого сегмента сети Интернет .
Запрос КоличестhkljZgbp luk)
Курсы & (Июнь | Джобс) |
Джобс & ( Июнь | Курсы) 2020
Курсы & Джобс 1500
Джобс & Июнь 800
Июнь & Курсы 1200
Какое минимальное количе стhkljZgbp  тыся чах) может быть найдено
по зап росу
Джобс & Курсы & Июнь ?
Считается, что k_aZijhku\uihegyebkvijZdlbq_kdbh^ghременно, так что
набор страниц, содержащих k_ искомые слоZ не изменялся за j_fy
uiheg_gbyaZijhkhy .

Решение :


Заметим, что пере сечение трех множестходит в о k_ij_^klZ\e_ggu_
множестZKe_^hательно, формула dexq_gbybkdexq_gby[m^_lbf_lv
следующую форму. х – мощность пересечения трех множест.

2020 = 1500 + 800 + 1200 – 2х

2х = 3500 – 2020 = 1480


Отв ет: ___________ 740 __ ___________.

Обозначим чер ез m & n поразрядную конъюнкцию неотрицательных целых
чисел m и n. Так, например, 12 & 6 = 1100 2 & 0110 2 = 0100 2 = 4.

Для какого набольшего целого неотрицательного числа А , меньшего 50 ,
ujZ`_gb_
(x & A ≠ 0) ˅ ( x & 21 ≠ 0) ˄ (x & 30 ≠ 0) ˅ ( x & 10 = 0)
истинно при любых целых неотрицательных значениях x?

Решение :
21 = 10101
30 = 11110
10 = 1010

Перейдем к форме для работы с битами числа
(�� & �� ≠ 0)∨(��4∨��2∨��0)∧(��4∨��3∨��2∨��1)∨��3̅̅̅∧��1̅̅̅

Вып олним преобразоZgby
(�� & �� ≠ 0)∨��4∨��2∨��0∧(��3∨��1)∨��3̅̅̅∧��1̅̅̅

(�� & �� ≠ 0)∨��4∨��2∨��0∨��3̅̅̅∧��1̅̅̅

Очеb^gh что  А перuc и третий биты должны быть раgu единице
одноj_f_ggh.

Найдем наибол ьшее число меньшее 5 0, в котором перucblj_lbcx иты = 1.

Максимальная степень двойки, которую мы можем добавить 2 5 = 32.
32 + 10 = 42

Из бито которые еще не использоZgu мы можем добавить lhjhc и
нулеhc.
32 + 8 + 4 + 2 + 1

Ответ: _______ 47______ ____________.
17 19 18

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 12 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

В пр ограмме используется одномерны й целочисленный масси A с
индексами от 0 до 1 0. Значения элементов массиZ$>L@ijbедены lZ[ebp_.
i 0 1 2 3 4 5 6 7 8 9 10
A[i] 5 8 11 14 17 20 23 26 29 32 35
Определите значение переменной s после u полнения следующего
фрагмента этой программы (запи санного ниже на четырех языках
программироZgby 
C++ Паскаль
s = 20 ;
for (int i = 4; i < 1 1; i++){
if(A[i] – A[i -4] > 0){
t := A[i];
A[i] : = A[i -4] + 25 ;
A[i -4] := t;
}
else s := s – 2;
}
s := 20 ;
for i := 4 to 1 0 do begin
if A[i] –A[ i-4] > 0 then
begin
t := A[i];
A[i] := A[i -4] + 25;
A[i -4] := t;
end
else s := s – 2;
end;
Python Бейсик
s = 20
for i in range( 4, 1 1):
if A[i] – A[i -4] > 0:
t = A[i]
A[i] = A [i -4] + 25
A[i -4] = t
else:
s = s - 2

S = 20
FOR I = 4 TO 1 0
IF A[I] -A[I -4] > 0 THEN
T = A[I]
A[I] = A[I -4] + 25
A[I -4] = t
ELSE
S = S – 2
END IF
NEXT I

Решение :
Заметим, что имеем дело с hajZklZxs_c последоZl_evghklvx. Элементы
4-7 однозн ачно больше тех, что на 4 пози ции ле__ поэтому на перuo
четырех итерациях uihegy_lky условие и алгоритм заменяет
соот_lkl\mxsb_we_f_glu.
i 0 1 2 3 4 5 6 7 8 9 10
A[i] 17 20 23 26 30 33 36 39 29 32 35
На остаrbokylj_obl_jZpbyo услоb_g_ыполняе тся.

Ответ: ________ 14______ __________.
Ниже на четырех языках программироZgbyaZibkZgZe]hjblfIhemqb на
oh^ натуральное десятичное число x, этот алгоритм печатает число S. Какое
наименьшее число х необходимо \_klb чтобы  рез ультате работы
алгор итма на экран было uедено чи сло, большее 100.
C++ Паскаль
#include
using namespace std;
int main(){
int x, A, B , S;
cin >> x;
B = x;
S = -2;
A = 4;
while ( B / 2 > 0 ) {
if( B % 2 == 0 )
S = S + A;
el se
S = S * 3 ;
B = B / 2;
}
cout << S << endl ;
return 0;
}
var x, A, B , S: integer;
begin
readln(x);
B := x;
S := -2;
A := 4;
while (B div 2) > 0 do
begin
if (B mod 2) == 0 then
S := S + A
else
S := S * 3;
B := B div 2;
end ;
writeln(S);
end.
Python Бейсик
x = int(input())
B = x
S = -2
A = 4
while B // 2 > 0 :
if B % 2 == 0:
S = S + A
else:
S = S * 3
B = B // 2
print( S)
DIM X, A, B, S AS INTEGER
INPUT X
B = X
S = -2
A = 4
WHILE B \ 2 > 0
IF B MOD 2 = 0 TH EN
S = S + A
ELSE
S = S * 3
END IF
B = B \ 2
WEND
PRINT S


20 20

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 13 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Решение :
Заметим, что в цикле идет обработка разрядов двоичного числа. Если
младший разряд четный (0), к значению переменной S добавляется значение
переменной А, в противном случае значение S увеличивается втрое.

Начальное значение переменной S = -2. Следовательно, первая операция –
прибавление А (4).
Необходимо получить наименьшее число. Это значит, что
А) в числе минимальное количество разрядов (числа большие 2 выгоднее
домножать на 3),
Б) значения разрядов минимально возможные (выгоднее 0, чем 1)

-2 + 4 = 2
2 + 4 = 6 (выгоднее, чем 2*3, так как значение разряда с +4 меньше)
6*3 = 18
18*3 = 54
54*3 = 162

Попробуем провести операцию в обратном порядке (начав рассуждение со
значения 102).

102 = 34*3
36 (34 некратно 3) = 12*3
12 = 4*3
4 = 0 + 4
0 = -4 + 4

Заметим, что последовательность операций ровно такая же.

Также важно отметить, что условие продолжения цикла – значение
целочисленного деления B на 2 больше 0. Следовательно, алгоритм выходит
из цикла при B = 1.

Значит начальное значение В = 1111002 = 6010

Ответ: ______ ___ 60_______________.
Сколько сущестm_l значений oh^ghc переменной k для которых
программа uедет такой же результат, как для k = 37 .
Для Вашего удобстZ пр ограмма при_^_gZ на четырех языках
программироZgby.
C++ Паскаль
#include
using na mespace std;
long F(long x) {
return x*(x+2)*(x -2) ;
}
long G(long x){
return 3*x – 5;
}

int main(){
long i, k ;
cin >> k;
i = 0;
while(F(i) < G(k))
i = i + 1;
cout << i << endl;
return 0;
}
var i, k : longint;
function F( x:longint):longint;
begi n
F := x*(x+2)*(x -2) ;
end;
function G(x:longint ):longint;
begin
G := 3*x – 5;
end;

begin
readln(k);
i := 1;
while F(i) < G(k) do
i := i + 1;
wri teln( i);
end.
Python Бейсик
def F( x):
return x*(x+2)*(x -2)

def G(x):
return 3*x - 5

k = int(input())
i = 0

while F(i) < G(k):
i = i + 1
print( i)
DIM I, K AS LONG

INPUT K
I = 0
WHILE F(I) < G(K)
I =I + 1
WEND
PRINT I

FUNCTION F( X)
F = X*(X + 2)*(X - 2)
END FUNCTION

FUN CTION G(X)
F = 3*X – 5
END FUNCTION


21

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 14 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Решение :
В первую очередь определимся, что выведет программа при k = 37.

Запишем условие выхода из цикла математически.
i3 – 4i ≥ 3*37 – 5
i3 – 4i ≥ 106

Найдем минимальное целое положительное значение i.
53 – 4*5 = 105
63 – 4*6 = 192

Следовательно, на экран будет выведено число 6.

Узнаем при каких значениях i результат работы программы будет
аналогичный.

53 – 4*5 < 3k – 5
63 – 4*6 ≥ 3k – 5

110 < 3k
197 ≥ 3k

k ≥ 37 (минимальное целое, удовлетворяющее условию продолжения)
k ≤ 65 (максимальное целое, удовлетворяющее условию выхода)

k ∈ [37; 65]

Целых значений в найденном промежутке 29


Ответ: ______ 29___________________.
Исполнитель Вычислитель преобразует число на экране.
У исполнителя есть д_dhfZg^u, которым прис h_gughf_jZ:
1. Прибаblv 3
2. Умножить на 3 и отнять 2
ПерZy команда у_ebqbает число на экране на 3, lhjZy – у_ebqbает
значение н а 3 и uqblZ_l 2 из по лученного числа . Программа для
Вычислителя – это последовательность команд.
Сколько сущестm_l пр ограмм, для которых при исходном числе 7
результатом является число 94? При этом траектория uqbke_gbc будет
содерж ать число 37 и не соде ржит числа 70 ?
Траектория uqbke_gbc программы – это последоZl_evghklv результатов
uiheg_gby k_o команд программы. Н апример, для программы 121 при
исходном числе 3 траектория будет состоять из чисел 6, 16 , 19.

Решение :
Заметим, что стратегия должна содержать число 37. Из числа 37 попасть в
94 можно только прибавляя 3 до тех пор, пока не получится
соответствующее условию задачи число.

Такая стратегия однозначно проходит через число 70.

Следовательно, стратегий, соответствующих условию, не существует.

Ответ: _______ 0________________ __.

22

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 15 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Дана система логических ураg_gbc
 ((x1 ˅ y1) → (x2 ≡ y2 )) ˄ x3  y3 = 1
 ((x2 ˅ y2) → (x3 ≡ y3)) ˄ x4  y4 = 1
 ((x3 ˅ y3) → (x4 ≡ y4)) ˄ x5  y5 = 1
 ((x4 ˅ y4) → (x5 ≡ y5)) ˄ x6  y6 = 1
 ((x5 ˅ y5) → (x6 ≡ y6)) ˄ x7  y7 = 1

где x1,x 2,…,x7, y1,x2,…,y7 – логические переменные. Найдите количестh
решений этой системы.

Решение :
После небольшого анализа системы понимаем, что пары (х3, y3), (х4, y4),
(х5, y5), (x6, y6), (x7, y7) могут принимать только значение (0, 1).

Поэтому для выражений 3, 4 и 5 однозначно определен набор переменных
(x3, y3, x4, y4, x5, y5, x6, y6, x7, y7) = (0, 1, 0, 1, 0, 1, 0, 1, 0, 1).

Рассмотри два первых выражения.
 ((x1 ˅ y1) → (x2 ≡ y2 )) ˄ 0  1 = 1
 ((x2 ˅ y2) → (0 ≡ 1)) ˄ 0  1 = 1

Преобразуем
(x1 ˅ y1) → (x2 ≡ y2 ) = 0
x2 ˅ y2 = 1

x1 ˅ y1 = 1
x2 ≡ y2 = 0
x2 ˅ y2 = 1
Для данной системы есть три набора для (х1, у1) и 2 набора для (х2, у2) при
которых система выполняется.


Ответ: _________ 6_____ ___________.

Не забудьте перенести k_ от_lu в бланк от_lh № 1 khhlетстbb
с инструкцией по uiheg_gbxjZ[hlu.

№ задания Отве т
1 248AC
2 yzwx
3 78
4 2
5 15
6 2122
7 4
8 44
9 32
10 2882
11 11
12 15
13 18
14 XX
15 14
16 10
17 740
18 47
19 14
20 60
21 29
22 0
23 6

23

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 16 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Часть 2
Для записи от_lh на задания этой части (24 –27) используйте БЛАНК
ОТВЕТОВ № 2. Запиш ите сначала номер задания (24, 25 и т. д.), а затем
полное решение. От_luaZibkuайте чётко и разборчиво.
На обработку п оступает натуральное число, не превышающее 10 9. Нужно написать
программу, которая выводит произведение нечетных разрядов в десятичной зап иси
введенного числа. Если таких цифр в числе нет, необходимо вывести « NO ».
Программист написал программу неправильно.

Последовательно выполните следующее.
1. Напишите, что выведет эта програм ма при вводе числа 671 .
2. Какое наименьшее число может быть u ведено при работе этой программы?
Приведите пример числа N, при вводе которого программа выведет такой от_l.
3. Найдит е допущенные программистом ошибки и исправьте их
Исправление ошибки должно затрагивать только строку, в которой находится
ошибка. Для каж дой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т.е. приведите правильный в ариант строки.
Известно, что в тексте программы нужно исправить не б олее двух строк так,
чтобы она стала работать правильно.
Достаточн о у казать ошибки и способ их исправления для одного языка
программирования.
Обратите внимание на то, что требуется найти о шибки в имеющейся программе, а
не написать свою, возможно, использую щую другой алгоритм решения.

Решение :
Проанализируем програ мму.
Алгоритм выходит из цикла, когда значение N меньше или равно единице.
Алгоритм заходит в условие, когда младший десятичный разряд яв ляется нечетным
или когда младший десятичный разряд больше t.
Следовательно, в переменной t по итогу могут быть и четны е знач ения.
Задача 1.
6
Задача 2.
1 135
Задача 3.
Python
Неправильная строка Исправленная строка
p = 0 p = 1
print(d) print(p)


C++ Pascal
#include
using namespace std;
int main(){
long int N, d, p, b ;
cin >> N;
p = 0; b = 0;
while(N > 0){
d = N % 10;
if( d % 2 == 1){
p = p * d;
b = 1;
}
N = N / 10;
}
if(b == 1) cout << d;
else cout << "NO";
}
var N, p, d, b : longi nt;
begin
read(N);
p := 0;
b := 0;
while N > 0 do begin
d := N mod 10;
if d mod 2 = 1 then
begin
p := p * d;
b := 1;
end;
N := N div 10;
end;
if b = 1 then write(d)
else write( 'NO ');
end.
Python Бейсик
N = in t(input())
p = 0
b = 0
while N > 0:
d = N % 10
if d % 2 == 1:
p = p * d
b = 1
N = N // 10
if b == 1:
pr int(d)
else:
print("NO")

DIM N , D, P, B AS LONG
INPUT N
P = 0
B = 0
WHILE N > 0
D = N % 10
IF D MOD 2 = 1 THEN
P = P * D
B = 1
END IF
N = N \ 10
WEND
IF B = 1 THEN
PRINT D
ELSE
PRINT("NO")
END IF
END


24

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 17 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Дан целочисленный масси из 30 элементо Элементы массиZ могут
принимать целые положительные значения от 1 до 10 000 de ючительно.
Напишите на одном из языко программироZgby программу, которая
исследует тройки, dhlhjuoторой элемент одноj_f_gghf| ньше перh]h
и третьего элементоbgZoh^blfbgbfZevguckj_^gbcwe_f_glIhke_q_]h
заменяет gZc^_gguoljhcdZokj_^g__ значение на найденное минимальное
значение и uодит полученный масси на экран по одному значению 
строке. Под тройкой подразумеZ| тся группа из трех подряд идущих
элементоfZkkbа.
Например, из массиw
7, 5, 7, 4, 8, 5, 14, 15
программа должна получить массив
7, 4, 7, 4, 8, 4, 14, 15
С++ Паскаль
#include
using namespace std;
const int N = 30;
int main() {
long a[N];
long i, k, m;
for (i = 0; i cin >> a[i];
...
return 0;
}
const N = 30;
var a: array [1..N] of
longint;
i, k , m: longint;
begin
for i := 1 to N do
readln(a[i]);
...
end.
Python Бейсик
# допускается также
# использоZlv^е
# пе реме нные k и m
a = []
n = 30
for i in range(0, n):

a.append(int(input()))
...
CONST N AS INTEGER = 30
DIM A (1 TO N) AS LONG
DIM I AS LONG,
K AS LONG,
M AS LONG
FOR I = 1 TO N
INPUT A(I)
NEXT I
...
END



Решение :
Паскаль
m := 10001;
for i := 2 to N -1 do
if (a[i] < a[i -1]) and (a[i] < a[i+1]) then
if a[i] < m then
m := a[i];

for i := 2 to N – 1 d o
if (a[i] < a[i -1]) and (a[i] < a[i+1]) then
a[i] := m;

for i := 1 to N do
writeln(a[i]);
Python
m = 10001
for i in range (1, n-1):
if a[i] < a[i -1] and a[i] < a[i+1]:
if a[i] < m:
m = a[i]

print(a[0])
for i in range( 1, n-1):
if a[ i] < a[i -1] and a[i] < a[i+1]:
a[i] = m
print(a[i])
print(a[n -1])
C++
m = 10001;
for(i = 1; i < N - 1; i = i + 1)
if ((a[i] < a[ i-1])&&(a[i] < a[i+1]))
if(a[i] < m)
m = a[i];

for(i = 1; i < N - 1; i = i + 1)
if((a[i] < a[i -1])&&(a[i] < a[i+1]))
a[i] = m;
if(i == 1) cout << a[0] << endl;
cout << a[i] << endl;
if(i == n – 2) cout << a[n -1];
}

25

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 18 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

ДZb]jhdZ Петя и Ваня, играют в следующую игру. Перед игроками лежит куча
камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок
может
а) добавить dmqmdZfgy,
б) увеличить количество камней в 2 раза.
У каждого игрока для совершения хода есть неог раниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не
менее 43. Ес ли при этом количество камней в куче не более 70, то победителем
считается игрок, сделавший последний ход. В противном случае победит елем
становится его противник. Напр имер, если в куче было 39 камней и Петя удвоил
количество камней, то победителем будет с читаться Ваня. В начальный момент
к куче S камней; 1 ≤ S ≤ 42.
Будем говорить, что игрок имеет выигрышную стратегию , если он может
u игра ть при любых ходах противника. Описать стратегию игрока – значит
описать, какой ход он должен сделать в любой ситуации, которая ему может
встретиться при различной игре противника.

Задание 1.
а) при каких значениях числа S Петя может выиграть h^bgo од?
Укажите k_lZdb_a начения и соответствующие ходы Пети .
б) У кого из игроков есть ub]jurgZykljZl_]byijb S = 39, 37, 35.

Задание 2.
У кого из игроков есть выигрышная стратегия при S = 21. Опишите
соответствующие ub]jurgu_kljZl_]bb.

Задание 3.
У к ого из игроков есть выигрышная стратегия при S = 10? Постройте дерево всех
партий, возможных при этой выигрышной стратегии (в виде рисунка или
таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество
камней в позиции

Решение :
1а. Необходимо прийти в диапазон [43; 70] одним ходом.
Ходом *2 из значений [22; 35]
Ходом +3 из значений [40; 42]

Ответ: [22; 35] ∪ [40; 42]

1б. 39 – Ваня.
Петя может сходить либо в 42, либо в 78. Чем гарантирует для Вани
возможность выиграть.
37 – Ваня
Петя может сходить либо в 40, либо в 74. Чем гарантирует для Вани
возможность выиграть.
35 – Петя.
Значение из п.1а.

2. Ваня
Петя может походить либо в 42, либо в 24. Оба значения являются
выгодными для Вани (п. 1а)

3. Петя


26

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 19 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Вам предлага ется два задания с похожими условиями: задание А и задание Б.
Вы можете решать оба задания или одно из них по своему вы бору. Задание Б
более сложное, его решение оценивается выше. Итоговая оценка выставляется
как максимальная из оценок за за дания А и Б.

А. Имеется набор данных, состоящий из 4 пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно числ о так, чтобы сумма была
четной, минимальной и не делилась на 3 . Если получить требуемую сумму
невозможно, в качестве ответа вывести 0.
На пишите программу для решения этой задачи. В этом варианте задания
оценивается только правильность программы, время рабо ты и размер
использованной памяти не имеют значения.
Максимальная оценка за правильную программу – 2 балла.

Б. Имеется набо р данных, сос тоящий из пар положительных чисел. Необходимо
выбрать из каждой пары ровно одно число так, чтобы сумма была четной,
мин имальной и не делилась на 3 . Если получить требуемую сумму невозможно,
в качестве ответа нужно выдать 0.
Напишите программу для решения э той задачи.
Постарайтесь сделать программу эффективной по времени и по используемой
памяти (или хотя бы по одной из эти х характеристик).
Программа считается эффективной по времени, если время работы программы
пропорциона льно количеству пар N, т.е. при увел ичении N  k раз время работы
программы должно увеличиваться не более, чем  k раз.
Программа считается эффективной по памяти, если размер памяти,
использованной в программе для хранения данных, не зависит от числа N и не
превышает 1 килобайта .
Максимальна я оценка за правильную программу, эффективную по времени и по
памяти, - 4 балла.
Мак симальная оценка за правильную прог рамму, эффективную по времени, но
не эффективную по памяти, - 3 балла.
Как в варианте А, так и в варианте Б программа должна напечатать о дно число
– минимальную возможную сум му, которая не кратна 3 (или 0, есл и такой сумм ы
не нашлось ).
НАПОМИНАЕМ! Не забуд ьте указать, к какому заданию относится каждая из
представленных вами программ.
Перед текстом программы кратко опишите Ваш а лгоритм решен ия, укажите
использованный язык программирования и его версию (Например, Free Pascal
2.6.4).

Входные данные
Для вариа нта А на вход программе подается 4 строк и, каждая из которых
содержит два натуральных числа, не превышающих 100.

Пример вхо дных данных д ля задачи А
1 2
2 3
3 4
3 6

Для варианта Б на вход программе в первой строке подается количество пар N
(1 ≤ N ≤ 100000 ). Каждая из следующих N строк содержит два натуральных
числа, не превышающих 100.

Пример входных данных для варианта Б:
4
1 2
2 3
3 4
3 6

Пример выходных данных для приведённых ur_ijbf_jh\\oh^guo^Zgguo:
10


27

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 20 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Решение :
Описание переменных
a – массив (список) для хранения минимальных сумм с остатком, равным
индексу элемента, которые можно добавить, заменив наименьшее число в
паре на наибольшее.
f – массив (список) для идентификации найденных ДО исследования
текущей пары сумм в массиве а.
ostR – остаток от деления разности (y - x) на 6
cur_ind – индекс, стоящий на ostR элементов правее от j

Логика работы:

Этап 1. Ввод и динамическая обработка значений

При вводе пары:
- х и у упорядочиваются по возрастанию,
x, y = map(int, input(). split())
if x > y:
x, y = y, x

- в переменной r сохраняется их разность.
r = y - x
- к значению s добавляется минимальное введенное число
s += x

- ostR хранит значение остатка от деления разности r на 6
ostR = r % 6

Далее идет динамическая обработка значений:
- определяется минимальное значение разности с остатком от деления на 6
(записывается во временную переменную),
m = a[ostR]
if a[ostR] > r:
m = r

- определяется, можно ли с помощью изменения НЕСКОЛЬКИХ элементов
в парах сократить смещение с определенным остатком (например, из
разностей с остатками 1 и 2 сделать разницу в 3 – a[1] + a[2] < a[3]),

for j in range(1, 6):
cur_ind = (j + ostR) % 6
if f[j] and a[j] + a[ostR] < a[cur_ind]:
a[cur_ind] = a[j] + a[ostR]

- минимальной разности присваивается значение временной переменной m.
a[os tR] = m

Вспомогательный массив f нужен, чтобы не проверять значение вновь
полученных разностей. Например, a[2] был не определен, но получилось
так, что старое значение a[1] и новое значение для ostR = 1 получают
новую разность для a[2]. В таком случае нельзя на следующей итерации
вложенного цикла осуществлять проверку на новое значение для a[3] как
a[2] + m. После проверки всех остатков массив f переопределяется.
for j in range(6):
f[j] = a[j] != 50005

Этап 2. Нахождение нужной суммы.
Если сумма минимальных значений не подходит под условие задачи,
необходимо провести постобработку массива с «добавочными» суммами.

Случай 1. Найденная сумма кратна 3.
Перебираем остатки 2 и 4, если значение суммы четное, и 1 и 5, если
нечетное.
m = 50005
ind = i*2 + s % 2 // 2 и 4 или 1 и 5
if ind % 3 != 0 : // 0 и 3 фильтруется условием
if m > a[ind]:
m = a[ind]

Случай 2. Найденная сумма не кратна 3.
Необходимо добавить четную «добавочную» сумму, так, чтобы свойство
кратности 3 не изменилось.
m = 50005
for i in range(3):
ind = i*2 // перебор четных чисел 0, 2, 4
if (3 - r) % 3 != ind % 3 : // сохранение кратности
if m > a[ ind ]:
m = a[ ind ]

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 21 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

Код на Python:

n = int (inp ut ())
a = [50005]*6
f = [False]*6
s = 0
for i in range(n):
x, y = map(int, input(). split())
if x > y:
x, y = y, x
s, r += x , y - x
ostR = r % 6
m = a[ostR]
if a[ostR] > r:
m = r
for j in range(1, 6):
cur_ind = (j + ostR) % 6
if f[j] and a[j] + a[ostR] < a[cur_ind]:
a[cur_ind] = a[j] + a[ostR]
a[os tR] = m
for j in range(6):
f[j] = a[j] != 50005
r = s % 3
if s % 2 != 0 or r == 0:
m = 50005
if r == 0:
for i in range(3):
ind = i*2 + s % 2
if ind % 3 != 0 and m > a[ind]:
m = a[ind]
else:
for i in range(3):
ind = i*2
if (3 - r) % 3 != ind % 3 and m > a[ ind ]:
m = a[ ind ]
if m != 50005:
s += m
else:
s = 0
print(s)
Код на Pascal

var n, i, t, x, y, s, r, ostR, j, cur_ind, ind, m:
longint;
a: array[0..5] of longint;
f: array[0..5] of boolean;

begin
readln(n);
for i := 0 to 5 do begin
a[i] := 50005; f[i] := false;
end;

s := 0;
for i := 1 to n do begin
readln(x, y);
if x > y then begin
t := x; x := y; y := t;
end;
s := s + x; r := y - x;
ostR := r mod 6;
m := a[ostR]
if m > r then m := r;
for j := 1 to 5 do begin
cur_ind := (j + ostR) mod 6;
if f[j] and (a[j] + a[ostR] < a[cur_ind]) then
a[cur_ind] := a[j] + a[ostR];
end;
a[ostR] := m;
for j := 0 to 5 do f[j] := a[j] <> 50005;
end;

if (s mod 2 <> 0) or (s mod 3 = 0) then begin
m := 50005;
if s mod 3 = 0 then
for i := 0 to 2 do begin
ind := i*2 + s mod 2;
if (ind mod 3 <> 0) and (m > a[ind]) then
m := a[ind];
end

Единый государственный экзамен, 2020 г. ИНФОРМАТИКА Вариант 18052020 22 / 22

Составил Евгений Джобс
Разреша ется свободное копирование g_dhff_jq_kdboh[jZah\Zl_evguop_eyo

else begin
r := s mod 3;
for i := 0 to 2 do begin
ind := i*2 + s mod 2;
if ((3 -r) mod 3 <> ind mod 3 )and (m > a[ind]) then
m := a[ind];
end;
end;
if m <> 50005 then s := m + s
else s := 0;
end;
writeln(s);
end.