Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

Реальные варианты ЕГЭ

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Тренировочные варианты «Школково». 2018 год

Задание 1

Вычислите значение выражения \(8E_{16} - 8B_{16}\). Ответ запишите в десятичной системе счисления.

\(8E_{16} - 8B_{16}=E_{16}-B_{16}=14_{10} - 11_{10} = 3\)

Ответ: 3

Задание 2

Миша заполнял таблицу истинности функции \((x \wedge \neg y) \vee (y \equiv z) \vee w\), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных \(w, x, y, z\).

\[\begin{array}{| l | l | l | l | l |} \hline \text{Перем.1} & \text{Перем. 2} & \text{Перем. 3} & \text{Перем. 4} & \text{Функция}\\ \hline ??? & ??? & ??? & ??? & F\\ \hline & & & 1 & 0\\ \hline 1 & 0 & 0 & 0 & 0\\ \hline 1 & 1 & 0 & & 0\\ \hline \end{array}\] Определите, какому столбцу таблицы соответствует каждая из переменных \(w, x, y, z\).

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

Рассмотрим данную функцию, т.к. везде используется и в таблице наша функция всегда ложна, то \(w = 0\), значит \(w\) — переменная 3.

\(y\) и \(z\) не должны иметь одинаковое значение чтобы \((y \equiv z)\) было ложно. Значит это переменные 1 и 4. А переменная 2 — \(x\). Тогда ответом может быть \(yxwz\) или \(zxwy\). \(zxwy\) не подходит т.к. тогда третья строка будет истиной.

Ответ: yxwz

Задание 3

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населенного пункта в другой. Отсутствие звездочки означает, что такой дороги нет.

Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населенным пунктам В и С на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Из рисунка видно, что есть 4 вершины с 3 связями (возможные значения 2, 4‚ 6, 7) и 3 вершины с двумя связями (возможные значения 1, 3 , 5).

1 связана с 6 и 7, 3 связана с 2 и 4, 5 связана с 4 и 7. Только 5 связана с «тройными» вершинами. которые связаны с остальными «двойными » вершинами значит Р это 5.

Тогда пусть В это 4. а С это 7‹ дальше легко восстановить остальные вершины и получится, что С это 2. а В это 6. Если взять другое предположение пусть В это 7„ а С это 4. то получится. что С это 6, а В это 2.

Т.к. просят записать их в порядке возрастания, то 26.

Ответ: 26

Задание 4

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведенных данных, сколько жителей родились в том же городе, что и их внук или внучка. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

Для решения задачи создадим дерево родителей и детей.

Теперь легко увидеть, кто из дедушек и бабушек родился в том же городе, что и их внуки. Это 75 Тамбов (внук 77 Тамбов) и 89 Тула (внук 82 Тула).

Ответ: 2

Задание 5

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В‚ Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б используются такие кодовые слова: А — 0; Б — 1011:

Укажите сумму длин кратчайших кодовых слов для букв В. Г. при которых код будет допускать однозначное декодирование

Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Построим дерево по условию фано.

По картинке видно, что одна из букв может иметь длину 2, а другая 3. Значит минимальная сумма — 5.

Ответ: 5

Задание 6

На вход алгоритма подается натуральное число \(N\). Алгоритм строит по нему новое число следующим образом:

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

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

Если \(N\) четное, в конец числа (справа) дописывается 10, в противном случае дописывается 01.

Например, двоичная запись 1001 числа 9 будет преобазована в 100101.

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

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

Для начала переведем \(102_{10}=1100110_2\). Последние две цифры — 10, значит, \(N\) должно быть четным. Посмотрим на \(11001\) — число нечетное. Значит, берем следующее число, не превышающее 102: \(101_{10}=1100101\), последние две цифры — 01, значит, \(N\) должно быть нечетным. \(11001_2=25_{10}\), число нечетное, тогда 101 и есть ответ.

Ответ: 101

Задание 7

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

\[\begin{array}{|c|c|c|c|c|c|} \hline &A&B&C&D&E\\ \hline 1&40&5&400&4&4\\ \hline 2&30&6&40& &3\\ \hline 3&20&8&=\$B\$4+C2&30&2\\ \hline 4&10&400&100&40&15\\ \hline \end{array}\\\]

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

Формула \(=\$B\$4+C2\) означает, что ячейка \(B4\) не меняется, а \(C2\) меняется и по столбцам, и по строкам. Когда скопируем из \(C3\) в \(D2\), получим формулу \(=\$B\$4+D1\). \(B4=400\), \(D1=4\), наш ответ \(400+4=404\).

Ответ: 404

Задание 8

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

\[\begin{array}{|l|l|l|} \hline Python&Pascal&C++\\ \hline s=80&var\;s,\;n:\;integer;&\#include\;<iostream>\\ n=0&begin&using\;namespace\;std;\\ while\;s+n<150:&s:=80;&int\;main()\{\\ \quad s=s-5&n:=0;&\quad int\; s=80,n=0;\\ \quad n=n+15&while\;s+n<150\;do&\quad while\;(s+n<150)\{\\ print(n)&begin&\quad\quad s=s-5;\\ &\quad s:=s-5;&\quad\quad n=n+15;\\ &\quad n:=n+15;&\quad \}\\ &end;&cout<<n<<endl;\\ &writeln(n);&return\;0;\\ &end.&\}\\ \hline \end{array}\]

Сумма \(s+n\) каждый шаг будет увеличиваться на 10. Значит, после 7 шага (\((150-80):10=7\)) она станет равна 150 и больше не зайдет в цикл. Так как по условию просят найти \(n\), то \(n=0+15\cdot7=105\).

Ответ: 105

Задание 9

Автоматическая камера производит растровые изображения рамером 800 на 600 пикселей. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Объем файла с изображением не может превышать 500 Кбайт без учета размера заголовка файла. Какое максимальное количество цветов можно использовать в палитре?

Всего в изображении пикселей \(K=800*600=480000=2^4\cdot3\cdot10^4\) пикселей. Т.к. всего изображение занимает \(I=\) 500 Кбайт \(=5\cdot10^2\cdot2^{13}\) бит, для того, чтобы узнать сколько бит тратится на 1 пиксель, разделим \(I\) на \(N\): \(\cfrac{5\cdot10^2\cdot2^{13}}{2^4\cdot3\cdot10^4}\approx8,5\). Значит, на один пиксель приходится 8 бит. Тогда количество цветов, которое можно использовать в палитре \(2^8=256\).

Ответ: 256

Задание 10

Все 4-буквенные слова, составленные из букв К, Л, Н, Т, Э записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. КККККК

2. КККККЛ

3. КККККН

4. КККККТ

5. КККККЭ

...

Под каким номером стоит ККЛКЛК?

Представим буквы как цифры и перейдем к системе счисления:

К — 0, Л — 1, Н — 2, Т — 3, Э — 4. Так как маскмиальная цифра — 4, наша система счисления пятеричная.

Переведем ККЛКЛК нашу СС: \(001010=1\cdot5^3+1\cdot5^1=130\). Так как отчет идет не с нулевого элемента, а с первого, номер слова будет на единицу больше. Тогда наш ответ 131.

Ответ: 131

Задание 11

Ниже на трёх языках программирования записан рекурсивный алгоритм F.
\[\begin{array}{|l|l|l|} \hline \text{C++}&\text{Python}&\text{Pascal}\\ \hline void\;F(int\;n)\{&def\;F(n):&Procedure\;F\;(n:integer);\\ \quad if\;(n>2)\{&\quad if\;n>2:&begin\\ \quad\quad std::cout<<n;&\quad\quad print(n)&\quad if\;n>2\;then\\ \quad\quad F(n/2);&\quad\quad F(n//2)&\quad begin\\ \quad\quad F(n-1);&\quad\quad F(n-1)&\quad\quad write(n);\\ \quad \}&&\quad\quad F(n\;div\;2);\\ \}&&\quad\quad F(n-1);\\ &&\quad end\\ &&end.\\ \hline \end{array}\]

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова \(F(7)\). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Напишем, что будет выводить функция при \(n\leq7\):

\[\begin{array}{|l|l|l|l|l|l|} \hline n&3&4&5&6&7\\ \hline output&3&43&543&63543&7363543\\ \hline \end{array}\]

 

Ответ: 7363543

Задание 12

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 111.81.88.168 адрес сети равен 111.81.88.160.

Найдите наименьшее значение последнего байта маски. Ответ запишите в виде десятичного числа.

Так как изменился только последний байт, остальные три равны по 255.

\(168_{10}=10101000_{2}\)

\(160_{10}=10100000_{2}\)

\[\begin{array}{l} 10101000\\ 111?0000\\ \hline 10100000\\ \end{array}\]

Там, где сохранились единицы значение бита маски равно 1. После знака вопроса гарантировано будут нули т.к. бит поменял значение с 1 на 0. На месте знака вопроса может быть как 1, так и 0. Нам нужно наименьшее число, поэтому \(?=0\).

\(11100000_{2}=224_{10}\)

Ответ: 224

Задание 13

При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. Пр этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт, это число одно и то же для всех пользователей.

Для хранения данных о 15 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных данных об одном пользователе? В ответ запишите только целое число — количество байт.

Для хранения данных о 15 пользователях потребовалось 300 байт, значит для хранения данных об одном пользователе необходимо \(300:15=20\) байт. Теперь определим, сколько весит пароль одного пользователя. Для этого определим сколько бит необходимо для хранения 26-символьного алфавита. \(2^4<26\), \(2^5>26\), значит, для хранения 26-символьного алфавита необходимо 5 бит. Так как каждый пароль состоит из 10 символов, всего пароль весит \(5\cdot10=50\) бит, т.е. \(50:8\approx6,...\) байт \(=7\) байт. Значит, для хранения дополнительных сведений потребуется \(20-7=13\) байт.

Ответ: 13

Задание 14

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

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

2) нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w, вторая проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение “истина”, в противном случае возвращает значение “ложь”.

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

\[\begin{array}{l} \text{НАЧАЛО}\\ \text{ПОКА нашлось (11111) ИЛИ нашлось (888)}\\ \quad\text{ЕСЛИ нашлось (11111)}\\ \quad\quad\text{ТО заменить (11111,88)}\\ \quad\text{ИНАЧЕ}\\ \quad\quad\text{ЕСЛИ нашлось (888)}\\ \quad\quad\quad\text{ТО заменить (888,8)}\\ \quad\quad\text{КОНЕЦ ЕСЛИ}\\ \quad\text{КОНЕЦ ЕСЛИ}\\ \text{КОНЕЦ ПОКА}\\ \text{КОНЕЦ}\\ \end{array}\]

Изначально строка состоит из 82 единиц. Каждый цикл программа будет заменять 5 единиц на 2 восьмёрки. Сделает она это 16 раз и останется 32 восьмёрки и 2 единицы. После программа будет заменять 3 восьмёрки на 1 восьмёрку. Сделает она это 15 раз и останется 8811. Это и есть ответ.

Ответ: 8811

Задание 15

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

Сколько существует различных путей из города А в город М, проходящих через город Л?

Будем писать у каждого города количество путей, ведущих к нему из города А:

Ответ: 19

Задание 16

Определите, сколько двоек содержится в троичной записи значения выражения:

\[9^{12}+3^8-3\]

Для начала стоить отметить, что любое десятичное число A в \(n\)-ой степени можно записать как единицу и \(n\) нулей в системе счисления с основанием A: \({A^n}_{10}={1\overbrace{00...000}^n}_A\)

Представим все числа как степени тройки:

\[3^{24}+3^8-3^1\]

Для начала выполним сложение:

\[\begin{array}{r} + \begin{array}{r} 1000..0000..0000\\ 100000000\\ \end{array}\\ \hline \begin{array}{r} 1\underbrace{0...0}_{15}100000000 \end{array} \end{array}\]

Вычтем из полученного \(3^1\):

\[\begin{array}{r} - \begin{array}{r} _{\,\,\,\cdot\,2\,2\,2\,2\,2\,2\,3\,\,}\\ 10...0100000000\\ 10\\ \end{array}\\ \hline \begin{array}{r} 1\underbrace{0....0}_{15}22222220 \end{array} \end{array}\\\]

В итоге получаем ответ — 7.

Примечание: при вычитании в недесятичной системе счисления, мы занимаем не “десяток”, а само основание системы счисления. В данном примере из второй единицы (она стоит в 8 разряде) мы занимаем три в соседний разряд, и затем из полученной “тройки” занимаем в следующий разряд, таким образом продолжая до разряда, под которым стоит единица другого числа.

Ответ: 7

Задание 17

В языке запросов поискового сервера для обозначения логической операции “ИЛИ” используется символ “\(|\)” а для обозначения логической операции ”И” — символ “\(\&\)”.

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

\[\begin{array}{| l | l |} \hline \text{Запрос} & \text {Найдено страниц}\\ \hline \text{Поле} & 90\\ \hline \text{Пшеница} & 83\\ \hline \text{Солнце} & 62\\ \hline \text{Поле $|$ Солнце} & 142\\ \hline \text{Пшеница \& Поле} & 20\\ \hline \text{Солнце \& Пшеница} & 0\\ \hline \end{array}\] Какое количество страниц будет найдено по запросу Поле \(|\) Пшеница \(|\) Солнце?

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

Получается, что нужно найти 1+2+3+4+5.

Мы знаем, что 2= 20, тогда 1 = 83 - 60, а 2 + 3 + 4 = 90, 5 = 2 + 3 + 4 + 5 - 2 -3 - 4 = 142 - 90 = 52.

Получаем 1 + 2 + 3 + 4 + 5 = 63 + 90 + 52 = 205.

Ответ: 205

Задание 18

Для какого наибольшего целого неотрицательного числа А выражение

\((A < x) \vee (x < y) \vee (y + 2x \neq 48)\)

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

Чтобы найти наибольшее целое неотрицательное число \(А\), при котором выражение будет тождественно истинно при любых целых неотрицательных \(x\) и \(у\), рассмотрим, в каких случаях условия \((y + 2x \neq 48)\) и \((x < y)\) ложны.

Тогда нужно найти все решения, когда \((y = 48 -2x)\) и \((x \geq y)\). Построим их на графике. Из графика видно, что решением являются \(16 \leq X \leq 24\). \(0 \leq Y \leq 16\).

Чтобы выражение подходило для всех неотрицательных \(x\) и \(y\), нужно чтобы \(16 \geq X\), тогда \(A\) должно быть равно 15, и \((A < x)\) всегда будет истино.

Ответ: 15

Задание 19

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

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

\[\begin{array}{| l | l | l |} \hline \textbf{Python} & \textbf{Pascal} & \textbf{C++}\\ \hline b = 0 & b := 0; & b = 0;\\ for\ i\ in\ range(1,10): & for\ i := 1 \ to \ 9 \ do & for (int \ i \ = \ 1; \ i \ < \ 10;\ i++)\\ \quad if \ A[i-1] \ <= \ A[i]: & \quad if \ A[i-1] \ <= \ A[i] \ then & \quad if (A[i-1] <= A[i])\{\\ \quad \quad t\ =\ A[i] & \quad begin &\quad \quad t\ =\ A[i];\\ \quad \quad A[i]\ =\ A[i-1] & \quad \quad t :\ =\ A[i]; & \quad \quad A[i]\ =\ A[i-1];\\ \quad \quad A[i-1]\ =\ t & \quad \quad A[i]\ := \ A[i-1]; & \quad \quad A[i-1]\ =\ t;\\ \quad \quad b\ =\ b\ +\ 1 & \quad \quad A[i-1]\ := \ t; & \quad \quad b++; \\ & \quad \quad b\ :=\ b\ +\ 1; & \quad \} \\ & \quad end; & \\ \hline \end{array}\]

В цикле проверяется является ли предыдущий элемент массива меньше, чем текущий, если да, то их меняют местами и увеличивают счетчик \(b\).

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

\[\begin{array}{| l | l |} \hline \text{Шаг} & \text{Действие}\\ \hline 1 & 2<3\ (3,2,5,3,7,8,4,2,5,1)\ b = 1\\ 2 & 2<5\ (3,5,2,3,7,8,4,2,5,1)\ b = 2\\ 3 & 2<3\ (3,5,3,2,7,8,4,2,5,1)\ b = 3\\ 4 & 2<7\ (3,5,3,7,2,8,4,2,5,1)\ b = 4\\ 5 & 2<8\ (3,5,3,7,8,2,4,2,5,1)\ b = 5\\ 6 & 2<4\ (3,5,3,7,8,4,2,2,5,1)\ b = 6\\ 7 & 2=2\ (3,5,3,7,8,4,2,2,5,1)\ b = 7\\ 8 & 2<5\ (3,2,5,3,7,8,4,5,2,1)\ b = 8\\ 9 & 2>1\ (3,5,3,7,8,2,4,2,2,1)\ b = 8\\ \hline \end{array}\]

Ответ: 8

Задание 20

Ниже на трёх языках программирования записан алгоритм. Получив на вход натуральное десятичное число \(x,\) этот алгоритм печатает два числа: C и B. Укажите наибольшее число n, при вводе которого алгоритм печатает сначала 25, а потом 3.

\[\begin{array}{|l|l|l|} \hline \text{C++}&\text{Python}&\text{Pascal}\\ \hline \#include\;<iostream>&n\;=\;int(input())&var\;b,\;c,\;n:integer;\\ using\;namespace\;std;&b\;=\;0&begin\\ int\;main()\{&c\;=\;1&\quad read(n);\\ \quad int\;b,\;c,\;n;&while\;n\;>\;0:&\quad b\;:=\;0;\\ \quad cin\;>>\;n;&\quad b\;=\;b+1&\quad c\;:=\;1;\\ \quad b\;=\;0;&\quad if\;n\;\%\;2\;!=\;0:&\quad while\;n\;>\;0\;do\\ \quad c\;=\;1;&\quad\quad c\;=\;c*(n\;\%\;8)&\quad begin\\ \quad while\;(n>0)\{&\quad n\;=\;n//8&\quad\quad b\;:=\;b+1;\\ \quad\quad b=b+1;&print(c)&\quad\quad if\;n\;mod\;2\;<>\;0\;then\\ \quad\quad if\;(n\;\%\;2\;!=\;0)\{&print(b)&\quad\quad c\;:=\;c*(n\;mod\;8);\\ \quad\quad\quad c=c*(n\;\%\;8);&&\quad\quad n\;:=\;n\;div\;8;\\ \quad\quad \}&&\quad end;\\ \quad\quad n=n//8;&&write(c);\\ \quad \}&&write(b);\\ \quad cout\;<<\;c\;<<\;endl\;<<\;b\;<<\;endl;&&end.\\ return\;0;&&\\ \}&&\\ \hline \end{array}\]

В восьмеричной записи n должно быть 3 цирфры так как цикл выполнится 3 раза.

Если n нечётное, то C умножается на последнюю цифру числа в восьмеричной СС.

C \(=25=5\cdot5. \) Следовательно в восьмиричной записи числа n две цифры были 5-ми.

Третья цифра должна быть чётная. Так как нам нужно максимальное число, что берём 6.

\(655_{8}=429_{10}\)

Ответ: 429

Задание 21

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

\[\begin{array}{|l|l|l|} \hline \text{C++}&\text{Python}&\text{Pascal}\\ \hline \#include\;<iostream>&import\;math&var\;a,\;b,\;t,\;M,\;R\;:longint;\\ \#include<cmath>&def\;F(x):&function\;F(x:\;longint):longint;\\ using\;namespace\;std;&\quad return\;math.fabs(math.fabs(x-6)+&begin\\ &\quad math.fabs(x+6)-16)+2&F:=abs(abs(x-6)+abs(x+6)-16)+2\\ long\;F(long\;x)\{&&end;\\ \quad return\;abs(abs(x-6)+&a\;=\;-20;\;b\;=\;20&\\ \quad +abs(x+6)-16)+2;\; \} &M=a;\;R=F(a)&begin\\ int\;main()\{&for\;t\;in\;range(a,b+1):&\quad a:=-20;\;b:=20;\\ \quad long\;a\;=\;-20,\;b\;=\;20;&\quad if\;(F(t)<= R):&\quad M:=a;\;R:=F(a);\\ \quad long\;M\;=\;a,\;R\;=\;F(a);&\quad\quad M=t;\;R=F(t)&\quad for\;t:=a\;to\;b\;do\;begin\\ \quad for\;(int\;t\;=\;a;\;t\;<=\;b;\;++t)\{&print(M+R)&\quad\quad if\;(F(t)<= R)\;then\;begin\\ \quad\quad if\;(F(t)<= R)\{ &&\quad\quad\quad M:=t;\\ \quad\quad\quad M\;=\;t;\;R\;=\;F(t); &&\quad\quad\quad R:=F(t);\\ \quad\quad \} &&\quad\quad end;\\ \quad \} &&\quad end;\\ \quad cout\;<<\;M+R;&&\quad write(M+R);\\ \quad return\;0;&&end.\\ \}&&\\ \hline \end{array}\]

Программа должна вывести сумму координат точки минимума функции \(f(x)=||x-6|+|x+6|-16|+2\) с наибольшей абсциссой. Наименьшее значение будет, если большой модуль равен 0. Значит \(x=8\) и \(x=-8.\) Берём \(x=8\) так как нам нужна наибольшая абсцисса. \(f(8)=2.\) Наш ответ: \(8+2=10.\)

Ответ: 10

Задание 22

Исполнитель Вычислитель преобразует число на экране.

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

1. Увеличить на 2.

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

3. Увеличить на 3.

Первая команда увеличивает число на экране на 2, вторая умножает его на 2, а третья умножает его на 3. Программа для Вычислителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 22 и при этом траектория вычислений содержит число 11?

Пусть \(R(n)\) — количество программ, которых число 2 преобразуют в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-2) + R(n-3)\) — если число не делится на 2.

\(R(n) = R(n-2) + R(n-3) + R(n:2)\) — если число делится на 2.

Заполним таблицу до 11:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{2} & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline \text{1} & 0 & 2 & 1 & 2 & 3 & 5 & 5 & 9 & 10 \\ \hline \end{array}\]

По условию дано, что траектория должна проходить через число 11, значит \(R(12) = 0\), так как число 12 из 11 мы не можем получить данными командами. Заполним таблицу до конца:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2} & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline \text{1} & 0 & 2 & 1 & 2 & 3 & 5 & 5 & 9 & 10 & 0 & 10 & 10 & 10 & 20 & 20 & 30 & 40 & 50 & 70 & 100\\ \hline \end{array}\] Отсюда получаем ответ — 100.

Ответ: 100

Задание 23

Сколько существует различных наборов значений логических переменных \(x1,\) \(x2,\) ..., \(x9,\) \(y1,\) \(y2,\) ..., \(y9,\) которые удовлетворяют всем перечисленным ниже условиям?

\[\begin{array}{l} x_1\vee y_1\equiv \neg (x_2\vee y_2)=1\\ x_2\vee y_2\equiv \neg (x_3\vee y_3)=1\\ x_3\vee y_3\equiv \neg (x_4\vee y_4)=1\\ x_4\vee y_4\equiv \neg (x_5\vee y_5)=1\\ x_5\vee y_5\equiv \neg (x_6\vee y_6)=1\\ x_6\vee y_6\equiv \neg (x_7\vee y_7)=1\\ x_7\vee y_7\equiv \neg (x_8\vee y_8)=1\\ x_8\vee y_8\equiv \neg (x_9\vee y_9)=1 \end{array}\]

Воспользуемся методом отображения:

На катинке отмечено какие наборы \(x_2y_2\) должны быть при различных значениях набора \(x_1y_1\) для того, чтобы равенство сохранялось.

Строим таблицу, где вместо значений наборов будем писать количество способов их получения:

Сумма последнего столбца равна 324. Это и есть наш ответ.

Ответ: 324

Задание 24

На обработку поступает натуральное число от 1 до \(10^9\). Нужно написать программу, которая выводит на экран наименьшую нечетную цифру числа. Если нечетных цифр нет, требуется на экран вывести <<NO>>. Программист написал программу неправильно. Ниже эта написанная им программа для Вашего удобства приведена на трех языках программирования.

\[\begin{array}{|l|l|l|} \hline Python&Pascal&C++\\ \hline N=int(input())&var\,digit,\,mindigit,\,n:\,longint;&\#include<iostream>\\ mindigit=N\%10&begin&using\,namespace\,std;\\ while\;N>0:&\quad read(N);&int\,main()\{\\ \quad digit=N\%10&\quad mindigit:=N\,mod\,10;&\quad long\,N,\,digit,\,mindigit;\\ \quad if\,digit\,\%2\;!=0:&\quad while\;N>0\,do\,begin&\quad cin>>N;\\ \quad \quad if\,digit<mindigit:&\quad\quad digit:=N\,mod\,10;&\quad mindigit=N\%10;\\ \quad \quad \quad digit=mindigit&\quad\quad if\,digit\,mod\,2<>0\,then&\quad while\,(N>0)\{\\ \quad N=N//10&\quad \quad \quad if\;digit<mindigit\;then&\quad \quad digit=N\%10;\\ if\;mindigit<=9:&\quad \quad \quad \quad digit:=mindigit;&\quad \quad if\;(digit\%2\;!=0)\\ \quad print(mindigit)&\quad \quad N:=N\;div\;10;&\quad \quad \quad if(digit<mindigit)\\ else:&\quad end;&\quad \quad \quad digit=mindigit;\\ \quad print(``NO")&\quad if\;mindigit<=9\;then&\quad \quad N=N/10;\\ &\quad \quad write(mindigit);&\quad \quad \}\\ &\quad else&\quad if(mindigit<=9)\\ &\quad \quad write(``NO");&\quad \quad cout<<mindigit<<endl;\\ &end.&\quad else\\ &&\quad \quad cout<<``NO"\;<<endl;\\ &&\}\\ \hline \end{array}\]

Выполните следующие задания:

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

2. Приведите пример такого числа, при вводе которого приведенная программа, несмотря на ошибки, выведет правильный ответ.

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

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

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

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

1) Подставим \(n=134\):

\[\begin{array}{|c|c|c|c|} \hline \text{\textnumero} \; \text{шага}&N&digit&mindigit\\ \hline 1&134&4&4\\ \hline 2&13&3&4\\ \hline 3&1&1&4\\ \hline \end{array}\]

Наш ответ — 4.

2) Программа выводит правильный ответ только если на вход подается число с минимальной и нечетной цифрой, например, 45.

3) Приведем исправленные строки на языке Pascal:

 

Неверно: \(mindigit:=n\;mod\;10;\)

Верно: \(mindigit:=10;\)

 

Неверно: \(digit:=mindigit;\)

Верно: \(mindigit:=digit;\)

Ответ: См. решение

Задание 25

Дан целочисленный массив из 30 элементов. Элемента массива могут принимать целые значения от -10 000 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит минимальный элемент массива кратный 5, а затем заменяет каждый элемент массива кратный 5 на найденный минимальный элемент. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести измененный массив, каждый элемент выводится с новой строки. Например, для исходного массива из шести элементов:

204

115

27

20

305

4

 

Программа должна вывести следующий массив:

204

20

27

20

20

4

 

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

\[\begin{array}{|l|l|l|} \hline Python&Pascal&C++\\ \hline \text{\# разрешается использовать}&const\;n=30;&\#include\;<iostream>\\ \text{\# целочисленные переменные j, k}&var&using\;namespace\;std;\\ a=[\;] & \quad a:\;array[1..n]\;of\;longint;&int\;main()\{\\ n=30 \text{ \# не разрешается менять значение n} &\quad i,j,k:\;longint;&\quad const\;int\;n=30;\\ for\;i\;in\;range\;(0,n):&begin&\quad int\;i,j,k;\\ \quad a.append(int(input()))&\quad for\;i:=1\;to\;n\;do&\quad for\;(i=0;i<n;i++)\\ ...&\quad \quad readln(a[i]);&\quad \quad cin>>a[i];\\ &\quad ...&...\\ &end.&\quad return\; 0;\\ &&\}\\ \hline \end{array}\]

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

Используем переменную \(k\) в качестве минимума. Значение минимума должно быть больше самого максимального числа, которое возможно, в нашем случае — 10001. Затем запускаем цикл по массиву и ищем наименьший элемент, кратный 5. После этого еще раз запускаем цикл по массиву и заменяем все его элементы, кратные 5, на найденный минимум, то есть \(k\). Затем запускаем последний цикл для печати.

 

Приведем решение на языке Pascal:

\[\begin{array}{l} k:=10001;\\ for\;i:=1\;to\; n\; do\\ \quad if\;(a[i]<k)\;and\;(a[i]\;mod\;5=0)\; then\\ \quad \quad k:=a[i];\\ for\;i:=1\;to\;n\;do\\ \quad if\;(a[i]\;mod\;5=0)\; then\\ \quad \quad a[i]:=k;\\ for\;i:=1\;to\;n\;do\\ \quad writeln(a[i]);\\ \end{array}\]

Ответ: См. решение

Задание 26

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

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 71.

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

В начальный момент в первой куче было 6 камней, а во второй \(S\), 1\(\leq\) S \(\leq\) 64;

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации. которая ему мож вс’гретигься при различной игре противника. В описание выигрышной стратегии не еледует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрьииными независимо от игры противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1.

а) Укажите все такие значения числа \(S\), при которых Петя может выиграть за один ход.

6) Укажите наименьшее значение числа \(S\), при котором Ваня может выиграть своим первым ходом, если известно, что Петя допустил ошибку. Опишите выигрышную стратегию Вани.

Задание 2.

Укажите значение \(S\), при котором у Пети есть выигрышная стратегия. Причём одновременно выполняются два условия:

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Для каждого указанного значения \(S\) опишите выигрышную стратегию Пети.

Задание 3.

Укажите значение \(S\), при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия. позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения \(S\) опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в куче. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии, Например, полное дерево игры не является верным ответом на это задание.

Задание 1.

а) Петя может выиграть первым ходом, если \(S = 22, \dots, 64\). При меньших значениях \(S\) первым ходом выиграть невозможно. Пете достаточно умножить число камней на 3 и выиграть первым ходом.

б) \(S = 8\), Петя может увеличить число камней в куче в 3 раза, тем самым допустит ошибку. Тогда Ваня умножает число камней на 3 и выигрывает. \(S\) не может быть меньше 8, так как при 7, если Петя увеличивает в 3 раза, то получает 21 камень, что не является выигрышной позицией для Вани.

Задание 2.

\(S = 21\). Выигрышная стратегия показана в таблице.

Задание 3.

\(S = 20\). При данном значении все условия выолняются. Выигрышная стратегия показана в таблице.

Ответ: 1. а)22...64, б)8 2. 21 3. 20

Задание 27

На вход программы поступают \(N \leq 1000\) натуральных чисел, каждое из которых не превышает 10000. Необходимо определить количество пар элементов \((a_i,a_j)\) этого набора, в которых \(1 \leq i < j \leq N,\) произведение, которых кратно 13, а номера чисел в последовательности отличаются не менее, чем на 5. Напишите эффективную по времени и по памяти программу для решения этой задачи.
Задача А (2 балла). Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел \(N\) \((3 \leq N \leq 1000).\) В каждой из последующих \(N\) строк записано одно натуральное число, не превышающее 10000.
Пример входных данных:
7
4
14
27
39
7
2
13
Пример выходных данных для приведённого выше примера входных данных:
2
В приведённом наборе из 7 чисел имеются две пары (4, 13) и (14, 13), в которых произведение кратно 13, и номера элементов в паре отличаются не менее, чем на 5.

2 балла

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

\[\begin{array}{|l|l|l|} \hline \text{C++}&\text{Python}&\text{Pascal}\\ \hline \text{\#include <iostream>}&\text{a=[ ]}&\text{program N\_27;}\\ \text{using namespace std;}&\text{k=0}&\text{var a:array [0..10000] of integer;}\\ \text{}&\text{n=int(input())}&\text{i, n, k, m, j:integer;}\\ \text{int main(void)\{}&\text{for i in range(0,n):}&\text{begin}\\ \quad\text{int i = 0, n, k = 0, j=0;}&\quad\text{a.append(int(input()))}&\quad\text{k := 0;}\\ \quad\text{cin $>>$ n;}&\text{for i in range(0,n-5):}&\quad\text{readln(n);}\\ \quad\text{int* a = (int*)malloc(n*sizeof(int));}&\quad\text{for j in range(i+5,n):}&\quad\text{for i := 0 to n - 1 do}\\ \quad\text{for (i = 0; i < n; ++i) \{}&\quad\quad\text{if a[i]*a[j]\%13==0:}&\quad\quad\text{readln(a[i]);}\\ \quad\quad\text{cin $>>$ a[i];}&\quad\quad\quad\text{k+=1}&\quad\text{for i := 0 to n - 6 do}\\ \quad\text{\}}&\text{print(k)}&\quad\text{begin}\\ \quad\text{for (i = 0; i < n - 5; ++i) \{}&\text{}&\quad\quad\text{for j := i + 5 to n - 1 do}\\ \quad\quad\text{for (j = i + 5; j < n; ++j) \{}&\text{}&\quad\quad\text{begin}\\ \quad\quad\quad\text{if (a[i] * a[j] \% 13 == 0)}&\text{}&\quad\quad\text{if (a[i]*a[j] mod 13 = 0) then}\\ \quad\quad\quad\quad\text{k++;}&\text{}&\quad\quad\quad\text{k := k + 1;}\\ \quad\quad\text{\}}&\text{}&\quad\quad\text{end;}\\ \quad\text{\}}&\text{}&\quad\text{end;}\\ \quad\text{cout $<<$ k;}&\text{}&\quad\text{writeln(k);}\\ \quad\text{return 0;}&\text{}&\text{end.}\\ \text{\}}&\text{}&\text{}\\ \hline \end{array}\]

 

4 балла

Создадим массив из 5 элементов и считаем в него первые 5 чисел. Следующее число для первого элемента является потенциальной парой, поэтому если этот элемент делится на 13, то мы прибавляем 1 к одному счётчику (g13), а если нет - к другому (g). Так мы будем хранить в памяти количество чисел, которые будут потенциальной парой для последующих (расстояние будет больше 5-ти). Потом считываем следующее число в x. Если оно делится на 13, то образовывает пару со всеми ранне считаными числами (кроме тех, что остались в массиве, чтобы соблюсти условие расстояния), тогда прибавляем количество всех раннее считанных чисел (g13+g) в счётчик пар. Если не делится на 13, то образовывает пару только с числами, которые делятся на 3 и к счётчику пар прибавляется g (количество чисел, не делящихся на 13). X помещается в массив. Так обрабатывается вся последовательнось.

\[\begin{array}{|l|l|l|} \hline \text{C++}&\text{Python}&\text{Pascal}\\ \hline \text{\#include <iostream>}&\text{a = [ ]}&\text{program N\_27;}\\ \text{using namespace std;}&\text{g = 0}&\text{var a:array [0..4] of integer;}\\ \text{int main(void)\{}&\text{g13 = 0}&\text{i, n, k, x, g, g13:integer;}\\ \quad\text{int i = 0, n, k = 0, x, g=0, g13=0;}&\text{x = 0}&\text{begin}\\ \quad\text{cin $>>$ n;}&\text{k = 0}&\quad\text{k := 0;}\\ \quad\text{int a[5];}&\text{n = int(input())}&\quad\text{g := 0;}\\ \quad\text{for (i = 0; i < 5; ++i) \{}&\text{for i in range(0,5):}&\quad\text{g13 := 0;}\\ \quad\quad\text{cin $>>$ a[i];}&\quad\text{a.append(int(input()))}&\quad\text{readln(n);}\\ \quad\text{\}}&\text{n -= 5}&\quad\text{n := n - 5;}\\ \quad\text{n -= 5;}&\text{for i in range(0,n):}&\quad\text{for i := 0 to 4 do}\\ \quad\text{for (i = 0; i < n; ++i) \{}&\quad\text{if a[i \% 5] \% 13 == 0:}&\quad\quad\text{readln(a[i]);}\\ \quad\quad\text{if (a[i \% 5] \% 13 == 0)}&\quad\quad\text{g13 += 1}&\quad\text{for i := 0 to n - 1 do}\\ \quad\quad\quad\text{g13 += 1;}&\quad\text{else:}&\quad\text{begin}\\ \quad\quad\text{else}&\quad\quad\text{g += 1}&\quad\quad\text{if a[i mod 5] mod 13 = 0 then}\\ \quad\quad\quad\text{g += 1;}&\quad\text{x = int(input())}&\quad\quad\quad\text{g13 := g13 + 1}\\ \quad\quad\text{cin $>>$ x;}&\quad\text{if x \% 13 == 0:}&\quad\quad\text{else}\\ \quad\quad\text{if (x \% 13 == 0)}&\quad\quad\text{k = k + g + g13}&\quad\quad\quad\text{g := g + 1;}\\ \quad\quad\quad\text{k = k + g + g13;}&\quad\text{else:}&\quad\quad\text{readln(x);}\\ \quad\quad\text{else}&\quad\quad\text{k += g13}&\quad\quad\text{if x mod 13 = 0 then}\\ \quad\quad\quad\text{k += g13;}&\quad\text{a[i \% 5] = x}&\quad\quad\quad\text{k := k + g + g13}\\ \quad\quad\text{a[i \% 5] = x;}&\text{print(k)}&\quad\quad\text{else}\\ \quad\text{\}}&\text{}&\quad\quad\quad\text{k := k + g13;}\\ \quad\text{cout $<<$ k;}&\text{}&\quad\quad\text{a[i mod 5] := x;}\\ \quad\text{return 0;}&\text{}&\quad\text{end;}\\ \text{\}}&\text{}&\quad\text{writeln(k);}\\ \text{}&\text{}&\text{end.}\\ \hline \end{array}\]

 

Ответ: См. решение