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

Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

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

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

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

В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от −100000 до 100000 включительно. Определите количество троек последова- тельности, в которых сумма элементов делится на максимальный элемент последовательно- сти, оканчивающийся на 3. В ответе запишите количество найденных троек, затем макси- мальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

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

F(n) = 1,            при n = 1;
F(n) = (n − 1) · F(n − 1),  если n > 1.

Определите значение выражения:

( F(10938) / 2 − F(10937) ) / F(10936)

Заданы два промежутка B = (390; 750) и C = [210; 575], лежащие на числовой прямой.

Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение \(((x \notin B)∧ (x \in C))→ (((x \notin A)∧ (x \in C))→ (x \in B)) \)истинно (т. е. принимает значение 1) при любом значении переменной x.

В терминологии сетей ТСP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети.

Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы.

Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.

Сеть задана одним из входящих в неё узлов с IP-адресом 146.180.173.153 и маской сети 255.192.0.0. Найдите наибольший в данной сети IP-адрес. В ответе укажите найденный IP- адрес без разделителей.

Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы за- писать: 11122344.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a₀, a₁, …, a_n−1}), включая специальный пустой символ a₀. Время работы исполнителя делится на дискретные такты. На каждом такте головка находится в одном из состояний множества Q = {q₀, q₁, …, q_n−1}. В начальный момент головка находится в начальном состоянии q₀.

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

Программа исполнителя задаётся в табличном виде. В первой строке перечислены все возможные символы текущей ячейки, в первом столбце — возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ — состояние» невозможна, клетка остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый — записываемый в текущую ячейку символ; второй — один из символов «L», «R», «N», «S» («L»/«R» — сдвиг влево/вправо, «N» — без сдвига, «S» — завершение работы после выполнения команды); третий — новое состояние головки. Сдвиг происходит после записи символа. Например, команда «0, L, q₃»: в текущую ячейку записывается «0», затем головка сдвигается влево и переходит в состояние q₃.

Пример. На ленте записано неизвестное ненулевое количество подряд идущих символов «Z», остальные ячейки заполнены пустым символом «λ»; головка находится справа от самого правого «Z». Программа

      λ          Z
q0   λ,L,q0     X,L,q1
q1   λ,S,q1     X,L,q1

заменяет все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности «X».

Выполните задание. На ленте в соседних ячейках записано двоичное представление числа 1024 без ведущих нулей. Ячейки справа и слева заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей справа от последовательности ячейке. Программа исполнителя:

      λ          0          1
q0   λ,L,q1
q1   λ,S,q1     1,L,q1     0,R,q2
q2   0,S,q2     0,R,q2     1,R,q2

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

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 200 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 85 536 серийных номеров потребовалось не менее 9 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров.

В ответе запишите только целое число.

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

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

Все пятибуквенные слова, составленные из букв А, К, Р, И, Л, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ААААА
2. ААААИ
3. ААААК
4. ААААЛ
5. ААААР
6. ...

Определите, под каким номером в этом списке стоит последнее слово, которое начинается с гласной буквы, содержит ровно две буквы И и не содержит ни одной буквы Р.
 

Рома записывает голосовое сообщение для своего брата. Перед отправкой сообщение оцифровывается в формате моно с частотой дискретизации 128 000 Гц и глубиной кодирования 16 бит. Определите наименьшее целое количество Мбайт, необходимое для сохранения сообщения в памяти (без учёта заголовка), если его длительность – 2 минуты 30 секунд. В ответе укажите только число.

Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат).

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

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

Повтори 4 [Вперёд 28 Направо 90 Вперёд 26 Направо 90]
Поднять хвост
Вперёд 12 Направо 90 Вперёд 13 Налево 90
Опустить хвост
Повтори 4 [Вперёд 67 Направо 90 Вперёд 76 Направо 90]

Определите площадь пересечения фигур, ограниченного заданными алгоритмом линиями.

 

Автомат получает на вход число N и преобразует его в число R.

• Строится двоичная запись числа N.
• Если сумма цифр двоичного числа нечетное число, то дописывается 01.
• Если сумма цифр двоичного числа четное число, то дописывается 10.
• Результат переводится в десятичную систему и он же является числом R.

Какое наименьшее число R, большее 123, может, быть результатом работы этой программы?

Для кодирования некоторой последовательности, состоящей из букв К, О, Р, Л, Ё, Н, Д, используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв Р и Д используются кодовые слова: Р – 10, Д – 11. Какова наименьшая возможная длина закодированной последовательности для слова КОРОЛЁНОК?

Поле Тип операции содержит значение Поступление или Продажа, а в поле Количество упаковок, шт. внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня.

Заголовок таблицы имеет следующий вид:

ID операции	Дата	ID магазина	Артикул	Количество упаковок, шт	Тип операции

Таблица «Товар» содержит информацию об основных характеристиках каждого товара.

Заголовок таблицы имеет следующий вид:

Артикул	Отдел	Наименование товара	Ед_изм	Количество в упаковке	Цена за упаковку

Таблица «Магазин» содержит информацию о местонахождении магазинов.

Заголовок таблицы имеет следующий вид:

ID магазина	Район	Адрес

Используя информацию из приведённой базы данных, определите общую выручку (в руб.) от продажи всех видов туалетной бумаги, бумажных салфеток сервировочных и бумажных полотенец в магазинах Западного района за период с 14 по 29 сентября включительно.

В ответе запишите только число.

(демо-2025) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:  \(d(A, B) = \sqrt{((x_2-x_1)^2+(y_2-y_1)^2}\)

Входные данные
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. 
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.

Выходные данные
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.

(ЕГЭ-2023) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в четыре раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 59. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 59 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 58.

Задание 19. Найдите такое значение S, при котором Петя не может выиграть за один ход, но Ваня выигрывает своим первым ходом после любого хода Пети.
Задание 20. Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21 Найдите наименьшее значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

(ЕГЭ-2023) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в три раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 88. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 88 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 87.

Задание 19. Найдите такое значение S, при котором Петя не может выиграть за один ход, но Ваня выигрывает своим первым ходом после любого хода Пети.
Задание 20. Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21 Найдите наименьшее значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

(А. Богданов) Два игрока, Папа и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Папа. За один ход игрок может добавить в кучу семь камней или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 100. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 100 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 99.

Задание 19. Укажите максимальное значение S, при котором Папа может выиграть своим первым ходом, но поддается, и Ваня выигрывает своим первым ходом.
Задание 20. Найдите два наименьших значения S, при которых у Папы нет выигрышной стратегии, а у Вани есть. Но Ваня ошибается и у Папы нет возможности еще раз поддаться он вынужден выиграть. Найденные значения запишите в ответе в порядке возрастания.
Задание 21 Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Папы;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

(А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 или 3 камня или удвоить количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 73. Игрок, первым получивший кучу из 73 или большего числа камней, считается победителем. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. В начальный момент в куче было S камней, 1 ≤ S ≤ 72.

Задание 19. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в порядке возрастания.
Задание 21 Найдите два наименьших значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в порядке возрастания.

(ЕГЭ-2022) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 165. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в куче будет 165 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 164.

Задание 19. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21 Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.