Решение заданий демо версии ЕГЭ по информатике с пояснениями

1. Сколько единиц в двоичной записи шестнадцатеричного числа 12F0₁₆?

Пояснение.

Переведем число 12F0₁₆ в двоичную систему счисления: 12F0₁₆ = 1001011110000₂.

Подсчитаем количество единиц: их 6.

Ответ: 6.

2. Логическая функция F задаётся выражением (¬z)∧x ∨ x∧y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

Перем. 2

Перем. 3

Функция

???

???

???

F

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала - буква, соответствующая 1-му столбцу; затем - буква, соответствующая 2-му столбцу; затем - буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и таблица истинности: Перем. 1

Перем. 2

Функция

???

???

F

0

0

1

0

1

0

1

0

1

1

1

1

Тогда 1-му столбцу соответствует переменная y, а 2-му столбцу соответствует переменная x. В ответе нужно написать: yx.

Пояснение.

Данное выражение является дизъюнкцией двух конъюнкций. Можем заметить, что в обоих слагаемых есть множитель x. Т. е. при x = 0 сумма будет равна 0. Так, для переменной x подходит только третий столбец.

Седьмое значение функции равно 0 при x = 1. Такое возможно только при z = 1, у = 0, т. е. переменная1 − z, а переменная2 − y.

Ответ: zyx.

3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

</

П1

П2

П3

П4

П5

П6

П7

П1

45

10

П2

45

40

55

П3

15

60

П4

10

40

20

35

П5

15

55

П6

55

60

20

55

45

П7

35

45

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число - так, как оно указано в таблице.

Пояснение.

Пункт В − единственный пункт с пятью дорогами, значит ему соответствует П6, а пункт Е − единственный с четырьмя дорогами, значит ему соответствует П4.

Длина дороги из П6 в П4 равна 20.

Ответ: 20.

4. Во фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько всего родных братьев и сестёр есть у Штольц Т. И.

ID

Фамилия_И.О.

Пол

1465

Дядюн М.Б.

Ж

1493

Баль А.П.

М

1560

Штольц И.Б.

М

1625

Ререх А.И.

Ж

1837

Штольц П.И.

М

1851

Радек П.А.

Ж

1885

Штольц Б.Ф.

М

1983

Чиж Д.К.

Ж

2216

Рерих Л.А.

Ж

2226

Штольц А.Б.

Ж

2398

Малеев К.Г.

М

2470

Баль П.А.

М

2607

Штольц Т.И.

Ж

2737

Панина Р.Г.

Ж

2759

Тесленко Г.Р.

Ж

2788

Рерих В.Б.

Ж

ID_Ребенка

1493

2470

1560

1837

1560

2607

1885

1465

1885

1560

1885

2226

1885

2788

1983

1465

1983

1560

1983

2226

1983

2788

2226

2470

2759

1837

2759

2607

2788

1851

2788

2216

1) 1

2) 2

3) 3

4) 0

Пояснение.

По первой таблице видно, что ID Штольц Т. И. равен 2607. Найдем во второй таблице в графе «ID_ребенка» номер Штольц Т. И. Видно, что его родители имеют ID 2759 и 1560. Теперь найдем в графе «ID_ребенка» братьев и сестер Штольц Т. И. Это человек с ID 1837.

Правильный ответ указан под номером 1.

Или

Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, среди которых также могут встречаться следующие символы:

Символ «?» (вопросительный знак) означает ровно один произвольный символ.

Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

В каталоге находятся 6 файлов:

mustard.map

mustard.mp3

catarsis.mp4

vitarcon.mp4

taras.mp3

star.mp3

Ниже представлено восемь масок. Сколько среди них таких, которым соответствуют ровно четыре файла из данного каталога? *tar*.mp*

*?tar?*.mp?

?*tar*.mp?*

*t*r*?.m?p*

???*???.mp*

???*???.m*

*a*.*a*

*s*.mp*

Пояснение.

Рассмотрим каждую маску:

Маске *tar*.mp* соответствуют 5 файлов: все кроме первого,

Маске *?tar?*.mp? соответствуют 3 файла: mustard.mp3, catarsis.mp4, vitarcon.mp4

Маске ?*tar*.mp?* соответствуют 4 файла: mustard.mp3, catarsis.mp4, vitarcon.mp4, star.mp3

Маске *t*r*?.m?p* соответствует 1 файл: mustard.map

Маске ???*???.mp* соответствуют 3 файла: mustard.mp3, catarsis.mp4, vitarcon.mp4

Маске ???*???.m* соответствуют 4 файла: mustard.map, mustard.mp3, catarsis.mp4, vitarcon.mp4

Маске *a*.*a* соответствует 1 файл: mustard.map

Маске *s*.mp* соответствуют 4 файла: mustard.mp3, catarsis.mp4, taras.mp3, star.mp3

Итого: 3 маски, которым соответствуют ровно четыре файла из данного каталога.

Ответ: 3.

5. По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:

А - 0, И - 00, К - 10, О - 110, Т - 111.

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА

2) ИКОТА

3) КОТ

4) ни одно из сообщений не подходит

Пояснение.

Закодируем каждое слово.

КАА - 1000

ИКОТА - 00101110

КОТ - 10110111

Слово КАА можно декодировать как КИ

Слово ИКОТА можно декодировать как ААКОТА

Слово КОТ никак нельзя декодировать по-другому.

Следовательно, ответ 3.

6. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия - справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите такое наименьшее число N, для которого результат работы алгоритма больше 125. В ответе это число запишите в десятичной системе счисления.

ИЛИ

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 2,

2. умножь на 5.

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5.

Например, программа 2121 - это программа

умножь на 5,

прибавь 2,

умножь на 5,

прибавь 2,

которая преобразует число 1 в число 37.

Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.

Пояснение.

Данный алгоритм приписывает в конце числа или 10, если изначально в его двоичной записи было нечетное количество единиц, или 00 если четное.

126₁₀ = 1111110₂ может получиться в результате работы алгоритма из числа 11111₂.

11111₂ = 31₁₀.

Ответ: 31.

ИЛИ

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

Если число не делится на 5, тогда получено через команду 1, если делится, то через команду 2.

22 + 2 = 24(команда 1)

20 + 2 = 22(команда 1)

4 * 5 = 20(команда 2)

2 + 2 = 4(команда 1)

Ответ: 1211.

7. Дан фрагмент электронной таблицы. Из ячейки D2 в ячейку E1 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке E1?

B

C

D

E

1

1

10

100

1000

2

2

20

200

=$B2+C$3

20000

3

3

30

300

3000

30000

4

4

40

400

4000

40000

Примечание. Знак $ обозначает абсолютную адресацию.

Пояснение.

Новая формула стала выглядеть так: =$B1+D$3. что, в свою очередь, равно 3010.

Или

Дан фрагмент электронной таблицы.A

B

C

1

2

4

2

= (B1 - A1)/2

= 2 - A1/2

= (C1 - A1)*2 - 4

Какое целое число должно быть записано в ячейке C1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2 : С2 соответствовала рисунку? Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.

Пояснение.

В ячейке А₂ будет значение 1. В ячейке В₂ будет значение 1. Из диаграммы следует, что значения в ячейке С₂ в 2 раза больше. Следовательно, из того, что 2 = (C1 - A1)*2 - 4, следует, что ответ 5.

8. Запишите число, которое будет напечатано в результате выполнения программы. Для Вашего удобства программа представлена на пяти языках программирования.

Пояснение.

Цикл while выполняется до тех пор, пока истинно условие s > 0, т. е. переменная s определяет, сколько раз выполнится цикл. Поскольку изначально s = 47, цикл выполнится 6 раз, следовательно, n = 6 · 4 + 1 = 25.

Ответ: 25.

9. Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 128×128 пикселей при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.

Пояснение.

Один пиксель кодируется 8 битами памяти.

Всего 128 * 128 = 2⁷ · 2⁷ = 2¹⁴ пикселей.

Объем памяти, занимаемый изображением 2¹⁴ * 8 = 2¹⁷ бит = 2¹⁴ байт = 2⁴ Кбайт = 16 Кбайт.

Ответ: 16.

Или

Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 30 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 4 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? В ответе запишите только целое число, единицу измерения писать не нужно.

Пояснение.

Пусть размер первого получившегося файла . Тогда размер второго - . То есть он будет передаваться в раза дольше. Пропускная способность канала в город Б выше в 4 раза, то есть время будет в 4 раза меньше, чем при передаче в город А. Итого получаем время:

10. Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Пояснение.

Пусть Х стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего 3 · 3 · 3 · 3 = 81 вариант.

Таким образом Х можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант.

Итого получается 81 · 5 = 405 слов.

Ответ: 405.

11. Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?

Пояснение.

Промоделируем работу программы:

F(11)

G(10): *

F(8)

G(7): *

F(5)

G(4): *

F(2)

G(1): *

12. В терминологии сетей TCP/IP маска сети - это двоичное число, меньшее 2³²; в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места нули. Маска определяет, какая часть IP-адреса узла сети относится к адресу сети, а какая - к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес - в виде четырёх байт, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32. 240.0.

Для узла с IP-адресом 224.128.112.142 адрес сети равен 224.128.64.0. Чему равен третий слева байт маски? Ответ запишите в виде десятичного числа.

Пояснение.

Рассмотрим третий слева байт в IP-адресе узла и адресе сети, представим их в двоичном виде:

112₁₀ = 0111 0000₂; 64₁₀ = 0100 0000_2.

Маской сети является такое двоичное число, которое при поразрядной конъюнкции с IP-адресом узла даст адрес сети. Таким числом является 1100 0000₂ = 192₁₀.

Ответ: 192.

13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов и содержащий только символы А, Б, В, Г, Д, Е. Каждый такой пароль в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит. Определите, сколько байт необходимо для хранения 20 паролей.

Пояснение.

Согласно условию, в пароле могут быть использованы 6 символов. Известно, что с помощью N бит можно закодировать 2^N различных вариантов. Поскольку 2² < 6 < 2³, то для записи каждого из 6 символов необходимо 3 бита.

Для хранения всех 11 символов пароля нужно 3 · 11 = 33 бита, а т. к. для записи используется целое число байт, то берём ближайшее не меньшее значение, кратное восьми, это число 40 = 5 · 8 бит = 5 байт.

Тогда для записи двадцати паролей необходимо 5 · 20 = 100 байт.

14. Исполнитель Редактор получает на вход строку цифр и преобразует её.

Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 127 идущих подряд цифр «9»? В ответе запишите полученную строку.

НАЧАЛО

ПОКА нашлось (333) ИЛИ нашлось (999)

ЕСЛИ нашлось (333)

ТО заменить (333, 9)

ИНАЧЕ заменить (999, 3)

КОНЕЦ ЕСЛИ

КОНЕЦ

Пояснение.

Данный алгоритм сначала заменит 9 первых девяток на три тройки, а затем заменит эти три тройки обратно на одну девятку. То есть, девять подряд идущих девяток заменяются на одну. Так из 127 девяток = 14 групп по 9 девяток и еще одна девятка - всего 15. Снова заменится еще одна группа из 9 девяток, итого осталось 7 девяток. Шесть первых будут заменены на две тройки, и останется строка 339.

Ответ: 339.

15. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Пояснение.

Начнем считать количество путей с конца маршрута - с города Ж. N_X - количество различных путей из города А в город X, N - общее число путей.

В "Ж" можно приехать из Е, К, З, В или Б, поэтому N = N_Ж = N_Е + N_К + N _З + N_В + N_Б (1)

Аналогично:

N_Е = N_Б + N_К;

N_К = N_З + N_И;

N_З = N_В + N_Г + N_Д;

N_В = N_А + N_Б = 1 + 1 = 2;

N_Б = N_А = 1.

Добавим еще вершины:

N_Г = N_А = 1;

N_Д = N_А + N_Г = 1 + 1 = 2;

N_И = N_З + N_Д = N_З + 2;

Преобразуем первые вершины с учетом значений вторых:

N_Е = N_Б + N_К = 1 + 12 = 13 ;

N_К = N_З + N_И = 2N_З + 2 = 10 + 2 = 12;

N_З = N_В + N_Г + N_Д = 2 + 1 + 2 = 5;

N_В = N_А + N_Б = 2;

N_Б = N_А = 1.

Подставим в формулу (1):

N = N_Ж = 13 + 12 + 5 + 2 + 1 = 33

16. Значение арифметического выражения: 9⁸ + 3⁵ - 9 - записали в систем счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Пояснение.

Преобразуем выражение:

(3²)⁸ + 3⁵ - 3²

3¹⁶ + 3⁵ - 3²

3¹⁶ + 3⁵ = 100...00100000

100...00100000 - 3² = 100...00022200

В полученном числе три двойки.

Ответ: 3

17. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» - символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос

Найдено страниц, тыс.

Математика & Информатика

330

Математика & Физика

270

Математика & (Информатика | Физика)

520

Какое количество страниц (в тысячах) будет найдено по запросу

Математика & Информатика & Физика?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Пояснение.

Запрос М & И также выдаёт и результаты по запросу М & И & Ф, так как второй является более узким запросом и подмножеством первого. Также и в случае с М & Ф.

То есть М & И = М & И & ¬Ф + М & И & Ф. (¬Ф - отсутствие Ф в запросе)

Также М & Ф = М & Ф & ¬И + М & Ф & И.

M & (И | Ф) = M & И & ¬Ф + М & Ф & ¬И + М & И & Ф.

Теперь можно заметить, что М & И & Ф = М & И + М & Ф - M & (И | Ф).

То есть М & И & Ф = 330 + 270 - 520 = 80.

18. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа Аформула

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменнойх)?

Пояснение.

Пусть

A: x&A ≠ 0; B: x&29 ≠ 0; C: x&12 ≠ 0.

Имеем: B → (¬C → A);

Упрощаем и получаем:

¬В + С + А = 1;

x&29₁₀ = 11101₂ при любом х ≠ 0;

x&12₁₀ = 01100₂ при любом х ≠ 0;

При поразрядной дизъюнкции ¬В: 00010₂ и С: 01100₂ имеем 01110.

Для выполнения равенства ¬В + С + А = 1 получаем: А: 10001₂, следовательно А = 17₁₀.

Ответ: 17.

19. В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 4, 7, 3, 8, 5, 0, 1, 2, 9, 6 соответственно, т.е. A[0] = 4, A[1] = 7 и т.д.

Определите значение переменной c после выполнения следующего фрагмента этой программы (записанного ниже на пяти языках программирования).

Пояснение.

Если A[i] элемент массива меньше A[0], то программа меняет их местами и увеличивает значение переменнойc на 1. Программа выполнится дважды, первый раз поменяв местами A[0] и A[2], так как 3<4, и второй раз поменяв A[0] и A[5] (0<3). Таким образом значение переменной с станет равно 2.

Ответ: 2.

20. Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого алгоритм печатает 26.

Пояснение.

В теле цикла числа M и L уменьшаются, пока не станут равными. Чтобы в итоге было напечатано 26, оба числа в какой-то момент должны быть равны 26. Пойдем от конца к началу: на предыдущем шаге одно число было 26, а другое 26 + 26 = 52. Еще на шаг раньше 52 + 26 = 78 и 52. До того 78 + 52 = 130 и 52. То есть наименьшее возможное число 130. А поскольку найденное число четное, то M будет присвоено значение 52, что и приведет к необходимому результату.

Ответ: 130.

21. Напишите в ответе число, равное количеству различных значений входной переменной k, при которых приведённая ниже программа выводит тот же ответ, что и при входном значении k = 10. Значение k= 10 также включается в подсчёт различных значений k. Для Вашего удобства программа приведена на пяти языках программирования.

Пояснение.

Для данного нужно найти минимальное такое, что . После чего если , то вывести , иначе .

При k = 10 имеем i = 3. Также i = 3 при всех .

В этом интервале k в правой части неравенства всегда будет .

То есть неравенство будет выполняться при . Нам же не нужно, чтобы оно выполнялось, так как при k = 10 оно не выполняется.

Итого при не выполняется и вывод всегда один и тот же - 2.

Большие i не рассматриваем, потому что нас интересует вывод 2, а при i > 3 этого не может быть.

Рассмотрим же i = 2. Для этого значения .

В правой части неравенства же стоит .

Нужно, чтобы новое неравенство выполнялось. Значит, .

Итого для i = 2 подходят .

При меньших вывод 2 также невозможен.

Итого имеем - всего 13 значений.

22. Исполнитель Май15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 - это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?

Траектория вычислений программы - это последовательность результатов

выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Пояснение.

Для ответа на задачу нужно найти количество программ, которые из 2 получают 14, количество программ, которые из 14 получают 29, не проходя при этом через 25, и перемножить найденные значения. Сначала найдём количество программ, получающих 14.

Обозначим R(n) - количество программ, которые преобразуют число 2 в число n.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(n - 1), так как существует единственный способ получения n из n - 1 - прибавление единицы.

2. Пусть n делится на 2.

Тогда R(n) = R(n / 2) + R(n - 1).

Теперь можно постепенно вычислить все значения:

R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(7) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(13) = 3 + 10 = 13.

Программа, получающая из числа 14 число 29, не проходящих через 25, одна: 21.

Таким образом, всего программ 13 · 1 = 13.

Ответ: 13.

23. Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₉, y₁, y₂, ... y₉, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x₁ ≡ y₁)) ≡ (x₂ ≡ y₂)

(¬ (x₂ ≡ y₂)) ≡ (x₃ ≡ y₃)

…

(¬ (x₈ ≡ y₈)) ≡ (x₉ ≡ y₉)

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₉, y₁, y₂, ... y₉, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Пояснение.

Заметим, что если переменные одной пары x₁, y₁ равны, то в следующей паре переменные не равны и наоборот. Таким образом, если x₁ = y₁, (т. е. наборы 0, 0 и 1, 1) то получаем 2⁹ наборов, так как у нас 9 пар переменных. Еще столько же наборов получим, если x1 ≠ y1. Итого, 2⁹ · 2 = 2¹⁰ = 1024 наборов.

Ответ: 1024.

24. На обработку поступает положительное целое число, не превышающее 10⁹. Нужно написать программу, которая выводит на экран сумму цифр этого числа, меньших 7. Если в числе нет цифр, меньших 7, требуется на экран вывести 0. Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования.

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 456.

2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ.

3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:

1) выпишите строку, в которой сделана ошибка;

2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки.

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

Пояснение.

Решение использует запись программы на Паскале. Допускается использование программы на любом из четырёх других языков.

1. Программа выведет число 4.

2. Пример числа, при вводе которого программа выдаёт верный ответ: 835.

Замечание для проверяющего. Программа работает неправильно из-за неверной выводимой на экран переменной и неверного увеличения суммы. Соответственно, программа будет работать верно, если в числе старшая цифра (крайняя левая) равна сумме цифр, меньших 7.

3. В программе есть две ошибки.

Первая ошибка. Неверное увеличение суммы.

Строка с ошибкой:

sum := sum + 1;

Верное исправление:

sum := sum + digit;

Вторая ошибка. Неверный вывод ответа на экран.

Строка с ошибкой:

writeln(digit)

Верное исправление:

writeln(sum)

25. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от -10 000 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм,

позволяющий найти и вывести количество пар элементов массива, в которых оба числа делятся на 3. В данной задаче под парой подразумевается два подряд идущих элемента массива.

Например, для массива из пяти элементов: 6; 2; 9; -3; 6 - ответ: 2.

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке

программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

Пояснение.

Будем бежать по массиву и хранить в переменной j, сколько на данный момент чисел подряд делится на 3. И если j больше 1, будем увеличивать на единицу переменную k - ответ на задачу.

Pascal.

j := 0;

k := 0;

for i := 1 to N do

begin

if a[i] mod 3 = 0 then

j := j + 1

else

j := 0;

if j > 1 then

k := k + 1;

end;

print(k);

Си.

j = 0;

k = 0;

for (i = 0; i < N; i++) {

if (a[i] % 3 == 0)

j++;

else

j = 0;

if (j > 1)

k++;

}

printf("%d", k);

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Пояснение.

Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32) после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32), (16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети

выигрывает своим первым ходом.

Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети. При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из начальных позиций (7, 32) и (8, 31). Петя после первого хода должен получить позицию (8, 32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.

Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.

27. В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число - текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.

Необходимо вычислить «бета-значение» серии показаний прибора - минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным -1.

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

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А.

Максимальная оценка за выполнение задания А - 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы

программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, - 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, - 3 балла. НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число N - общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число - очередное показание прибора.

Пример входных данных:

11

12

45

5

3

17

23

21

20

19

18

17

Программа должна вывести одно число - описанное в условии произведение либо -1, если получить такое произведение не удаётся.

Пример выходных данных для приведённого выше примера входных данных:

54

Пояснение.

Задание Б (решение для задания А приведено ниже, см. программу 4). Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные - только с чётными.

Для каждого показания с номером k, начиная с k = 7, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k - 6. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное - только чётным.

Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 6 элементов ранее, и выбрать минимальное из всех таких произведений.

Поскольку каждое текущее минимальное показание используется после ввода ещё 6 элементов и после этого становится ненужным, достаточно хранить только 6 последних минимумов. Для этого можно использовать массив из 6 элементов и циклически заполнять его по мере ввода данных. Размер этого массива не зависит от общего количества введённых показаний, поэтому такое решение будет эффективным не только по времени, но и по памяти. Чтобы хранить абсолютный и чётный минимумы, нужно использовать два таких массива. Ниже приводится пример такой программы, написанной на алгоритмическом языке.

Пример 1. Пример правильной программы на алгоритмическом языке. Программа эффективна и по времени, и по памяти.

алг

нач

цел s = 6 | требуемое расстояние между показаниями

цел amax = 1001 | больше максимально возможного показания

цел N

ввод N

цел a | очередное показание прибора

целтаб мини[0:s-1] | текущие минимумы последних s элементов

целтаб миничет[0:s-1] | чётные минимумы последних s элементов

цел i

| вводим первые s показаний, фиксируем минимумы

цел ма; ма := amax | минимальное показание

цел мчет; мчет := amax | минимальное чётное показание

нц для i от 1 до s

ввод а

ма := imin(ма, a)

если mod(a,2) = 0 то мчет := imin(мчет,a) все

мини[mod(i, s)] := ма

миничет[mod(i, s)] := мчет

кц

цел мп = amax*amax | минимальное значение произведения

цел п

нц для i от s+1 до N

ввод а

если mod(a,2)=0

то п := a * мини[mod(i, s)]

иначе если мчет < amax

то п := a * миничет[mod(i, s)]

иначе п := amax*amax;

все

все

мп := imin(мп, п)

ма := imin(ма, a)

если mod(a,2) = 0 то мчет := imin(мчет,a) все

мини[mod(i, s)] := ма

миничет[mod(i, s)] := мчет

кц

если мп = amax*amax то мп:=-1 все

вывод мп

кон

Возможны и другие реализации. Например, вместо циклического заполнения массива можно каждый раз сдвигать его элементы. В приведённом ниже примере хранятся и сдвигаются не минимумы, а исходные значения. Это требует чуть меньше памяти (достаточно одного массива вместо двух), но по времени решение со сдвигами менее эффективно, чем с циклическим заполнением. Однако время работы остаётся пропорциональным N, поэтому максимальная оценка за такое решение тоже составляет 4 балла.

Программа 2. Пример правильной программы на языке Паскаль.

Программа использует сдвиги, но эффективна по времени и по памяти

const s = 6; {требуемое расстояние между показаниями}

amax = 1001; {больше максимально возможного показания}

var

N: integer;

a: array[1..s] of integer; {хранение s показаний прибора}

a_: integer; {ввод очередного показания}

ma: integer; {минимальное число без s последних}

me: integer; {минимальное чётное число без s последних}

mp: integer; {минимальное значение произведения}

p: integer;

i, j: integer;

begin

readln(N);

{Ввод первых s чисел}

for i:=1 to s do readln(a[i]);

{Ввод остальных значений, поиск минимального произведения}

ma := amax; me := amax;

mp :=amax*amax;

for i := s + 1 to N do begin

readln(a_);

if a[1] < ma then ma := a[1];

if (a[1] mod 2 = 0) and (a[1] < me) then me := a[1];

if a_ mod 2 = 0 then p := a_ * ma

else if me < amax then p := a_ * me

else p := amax* amax;

if (p < mp) then mp := p;

{сдвигаем элементы вспомогательного массива влево}

for j := 1 to s - 1 do

a[j] := a[j + 1];

a[s] := a_

end;

if mp = amax*amax then mp:=-1;

writeln(mp)

end.

Если вместо небольшого массива фиксированного размера (циклического или со сдвигами) хранятся все исходные данные (или все текущие минимумы), программа сохраняет эффективность по времени, но становится неэффективной по памяти, так как требуемая память растёт пропорционально N. Ниже приводится пример такой программы на языке Паскаль. Подобные (и аналогичные по сути) программы оцениваются не выше 3 баллов.

Программа 3. Пример правильной программы на языке Паскаль. Программа эффективна по времени, но неэффективна по памяти

const s = 6; {требуемое расстояние между показаниями}

amax = 1001; {больше максимально возможного показания}

var

N, p, i: integer;

a: array[1..10000] of integer; {все показания прибора}

ma: integer; {минимальное число без s последних}

me: integer; {минимальное чётное число без s последних}

mp: integer; {минимальное значение произведения}

begin

readln(N);

{Ввод всех показаний прибора}

for i:=1 to N do readln(a[i]);

ma := amax;

me := amax;

mp := amax*amax;

for i := s + 1 to N do

begin

if a[i-s] < ma then ma := a[i-s];

if (a[i-s] mod 2 = 0) and (a[i-s] < me) then

me := a[i-s];

if a[i] mod 2 = 0 then p := a[i] * ma

else if me < amax then p := a[i] * me

else p := amax * amax;

if (p < mp) then mp := p

end;

if mp = amax*amax then mp := -1;

writeln(mp)

end.

Возможно также переборное решение, в котором находятся произведения всех возможных пар и из них выбирается минимальное. Ниже (см. программу 4) приведён пример подобного решения. Это (и аналогичные ему) решение неэффективно ни по времени, ни по памяти. Оно является решением задания А, но не является решением задания Б. Оценка за такое решение - 2 балла.

Программа 4. Пример правильной программы на языке Паскаль. Программа неэффективна ни по времени, ни по памяти

const s = 6; {требуемое расстояние между показаниями}

var

N: integer;

a: array[1..10000] of integer; {все показания прибора}

mp: integer; {минимальное значение произведения}

i, j: integer;

begin

readln(N);

{Ввод значений прибора}

for i:=1 to N do

readln(a[i]);

mp := 1000 * 1000 + 1;

for i := 1 to N-s do begin

for j := i+s to N do begin

if (a[i]*a[j] mod 2 = 0) and (a[i]*a[j] < mp)

then mp := a[i]*a[j]

end;

end;

if mp = 1000 * 1000 + 1 then mp := -1;

writeln(mp)

end.