ЕГЭ_информатика

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

• добавить в кучу два камня;
• добавить в кучу пять камней;
• увеличить количество камней в куче в два раза.

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

В начальный момент в куче было S камней, где 1 ≤ S ≤ 102. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.

Квадрат разлинован на N × N клеток, где 1 < N < 30. Исполнитель Робот начинает движение в левой верхней клетке и должен попасть в правую нижнюю клетку.

За одно перемещение Робот выполняет одну из двух команд: «вправо» — переходит в соседнюю клетку справа, или «вниз» — переходит в соседнюю клетку снизу. Квадрат ограничен внешними стенами. Между соседними клетками могут находиться внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском в каждой клетке лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает её монету. Это относится и к начальной, и к конечной клетке маршрута.

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

Исходные данные представлены электронной таблицей размером N × N; каждая её ячейка соответствует клетке поля. Внутренние и внешние стены обозначены утолщёнными линиями. В ответе запишите сначала максимальную, затем минимальную сумму.

Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

В файле содержится последовательность натуральных чисел. Её элементы принимают значения от 1 до 100 000 включительно. Каждое число записано в отдельной строке; заголовка нет.

Определите количество пар последовательности, в которых оба элемента строго меньше среднего арифметического всех элементов последовательности. Затем определите максимальную сумму элементов среди таких пар.

Под парой понимаются два идущих подряд элемента последовательности. Среднее арифметическое равно сумме всех элементов, делённой на их количество. Гарантируется, что подходящая пара существует.

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

Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки. 
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.

Алгоритм вычисления функции F(n), где n — натуральное число, задан следующими соотношениями:

• F(1) = 3;
• F(n) = F(n − 1) + n, если n > 1 и n чётно;
• F(n) = F(n − 1) + 2n, если n > 1 и n нечётно.

Чему равно значение выражения F(2026) − F(2022)? В ответе запишите целое число.

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n: в двоичной записи результата единица стоит только в тех разрядах, в которых единицы есть у обоих операндов. Например, 6 & 3 = 2, поскольку 110₂ & 011₂ = 010₂.

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

((x & 77) ≠ 0) → (((x & 37) = 0) → ((x & A) ≠ 0))

тождественно истинно, то есть принимает значение 1 при любом целом неотрицательном x? В ответе запишите A в десятичной системе счисления.

Значение арифметического выражения

5⁸⁰ + 5³⁰ − x,

где x — целое положительное число, не превышающее 1000, записали в системе счисления с основанием 5 без ведущих нулей.

Определите наибольшее значение x, при котором в полученной записи содержится ровно 51 цифра 0. В ответе запишите найденное значение x в десятичной системе счисления.

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

Команда "Прибавить 1" увеличивает число на экране на 1. Команда "Умножить на 2" применяется только тогда, когда число на экране нечётно, и увеличивает это число в два раза. К чётному числу команда B неприменима.

Программа для исполнителя — последовательность допустимых команд. Траектория вычислений — последовательность результатов выполнения всех команд программы. Например, программа BA при исходном числе 3 имеет траекторию 6, 7.

Сколько существует программ, для которых при исходном числе 2 результатом является число 31? В ответе запишите целое число.

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

Время работы исполнителя делится на дискретные такты — шаги. На каждом такте головка находится в одном из допустимых состояний q₀, q₁, … . В начальный момент головка находится в состоянии q₀.

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

Программа задаётся таблицей. В первой строке перечислены символы алфавита, в первом столбце — состояния головки. В клетке на пересечении строки состояния и столбца символа находится выполняемая команда. Если сочетание символа и состояния при работе программы невозможно, клетка остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми:

1. символ, записываемый в текущую ячейку;
2. направление: L — сдвиг на одну ячейку влево, R — сдвиг на одну ячейку вправо, S — завершение работы после записи символа без сдвига;
3. состояние, в которое переходит головка.

Например, команда X, L, q2 означает: записать X в текущую ячейку, сдвинуться в соседнюю слева ячейку и перейти в состояние q₂. Запись символа производится до сдвига.

Пример выполнения программы

Пусть на ленте подряд записаны три символа Z, остальные ячейки пусты, головка находится на первой пустой ячейке справа от слова ZZZ в состоянии q₀. Для этой иллюстрации используется следующая программа:

Начальное расположение ленты и головки:

Лента и головка после остановки:

Головка перемещается влево, заменяет все Z на X и останавливается на первой пустой ячейке слева от слова XXX. Пример поясняет правила чтения таблицы и не является программой основного задания.

Выполните задание

На ленте в соседних ячейках записано двоичное представление числа 1733 без ведущих нулей. Все остальные ячейки заполнены пустым символом λ. В начальный момент головка находится в состоянии q₀ в ближайшей пустой ячейке справа от записи числа.

Программа работы исполнителя:

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

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

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

Для хранения идентификаторов выделено 192 Кбайт памяти. Определите максимальное количество объектов, идентификаторы которых можно сохранить в этой памяти. В ответе запишите целое число. Считать, что 1 Кбайт = 1024 байт.

Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Числа не превышают 1000. Таблица не содержит строки заголовков.

Определите количество строк, для которых одновременно выполнены оба условия:

• в строке ровно три чётных и три нечётных числа;
• сумма чётных чисел строки больше суммы её нечётных чисел.

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

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

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

Камера формирует растровое изображение размером 1408 × 900 пикселей. Изображение может содержать 200 различных цветов. Для кодирования цвета каждого пикселя используется одинаковое и минимально возможное количество бит.

Коды пикселей записываются подряд без промежутков. Сжатие не производится; служебная информация и заголовок файла не учитываются.

Определите наименьшее целое количество Кбайт, достаточное для хранения одного такого изображения. В ответе запишите только число. Считать, что 1 Кбайт = 1024 байт, 1 байт = 8 бит.

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

У исполнителя имеются команды:

• Поднять хвост — перейти к перемещению без рисования.
• Опустить хвост — перейти в режим рисования.
• Вперёд n — переместиться на n единиц в направлении головы; Назад n — на n единиц в противоположном направлении, не меняя направления головы.
• Направо m — повернуть на m градусов по часовой стрелке; Налево m — на m градусов против часовой стрелки.

Здесь n и m — целые числа. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что указанная последовательность команд выполняется k раз.

Черепахе дан следующий алгоритм:

Повтори 4 [Вперёд 26 Направо 90 Вперёд 18 Направо 90]
Поднять хвост
Вперёд 8
Направо 90
Вперёд 6
Налево 90
Опустить хвост
Повтори 2 [Вперёд 30 Направо 90 Вперёд 25 Направо 90]

Определите количество точек с целочисленными координатами, находящихся строго внутри области пересечения фигур, ограниченных линиями этого алгоритма. Точки на границе пересечения учитывать не нужно.

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

1. Строится двоичная запись числа N без ведущих нулей.
2. Последняя цифра этой записи переносится в её начало. Порядок остальных цифр не меняется.
3. Полученная запись рассматривается как двоичная запись числа R. Ведущий нуль, если он появился, не влияет на значение числа. Результат переводится в десятичную систему счисления.

Например, для N = 13₁₀ = 1101₂ получается запись 1110₂, то есть R = 14. Для N = 10₁₀ = 1010₂ получается запись 0101₂, то есть R = 5.

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

По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Г, Д и Е. Для передачи используется неравномерный двоичный код, удовлетворяющий следующему условию: никакое кодовое слово не является концом другого кодового слова. Это условие позволяет однозначно декодировать сообщение, начиная с его правого конца.

Кодовые слова некоторых букв известны:

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

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

Миша заполнял таблицу истинности логической функции F

\(F = (x \land \neg y) \lor (y \equiv z) \lor w\),

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу соответствует каждая из переменных w, x, y, z. Некоторые значения в таблице пропущены.

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

Например, для функции ¬x ∨ y строка с первым значением 0, вторым значением 1 и значением функции 0 соответствует порядку переменных yx. Этот пример не относится к исходной функции F.