Экзамены и диагностики

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

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 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 сентября включительно.

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

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

В первой строке задано натуральное число \(n\) (\(1 \le n \le 1000\)) — количество чисел в последовательности. В каждой из следующих \(n\) строк записано одно натуральное число, не превышающее 30 000.

Программа должны вывести в первой строке количество чисел, восьмеричная запись которых оканчивается на 7. Во второй строке -  их среднее арифметическое с точностью до одного знака после запятой.

Напишите программу, которая в последовательности натуральных чисел определяет количество и сумму чисел, оканчивающихся на 7 в девятеричной системе счисления, находит среди них второй по величине элемент и сравнивает их среднее арифметическое со средним арифметическим остальных элементов последовательности. Сначала вводится количество чисел N (2 ≤ N ≤ 1000), затем N натуральных чисел, не превышающих 10 000.
В первой строке программа должна вывести через пробел количество и сумму чисел, оканчивающихся на 7 в девятеричной системе счисления. Во второй строке программа должна вывести второй по величине элемент среди таких чисел (если все они равны или такое число одно — программа должна вывести это значение). В третьей строке программа должна вывести YES, если среднее арифметическое чисел, оканчивающихся на 7 в девятеричной системе счисления, строго меньше среднего арифметического остальных элементов последовательности, и NO в противном случае. Гарантируется, что в последовательности есть хотя бы одно число, оканчивающееся на 7 в девятеричной системе счисления, и хотя бы одно число, не оканчивающееся на 7 в девятеричной системе счисления.

Формат входных данных

В первой строке число N. В следующих N строках — натуральные числа.

Формат выходных данных

В первой строке через пробел количество и сумма таких чисел. Во второй строке второй по величине элемент. В третьей строке YES или NO.

(демо-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 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.

Петя может проспать первый урок, если количество решенных домашних заданий вчерашним вечером дает нечётный остаток при делении на 3. Мама записывала количество решённых заданий в течении N последних дней и теперь хочет знать сколько уроков Петя проспал и какое максимальное  количество заданий он выполнил за один вечер, который предшествовал утру, когда Петя проспал.

Программа получает на вход количество дней (N), в течении которых мама записывала количество решенных заданий. Далее программа получает на вход N натуральных чисел - количество решенных домашних заданий в каждый из дней. Все числа натуральные и не превышают 10.

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


Наука доказала, что 0 заданий — самый безопасный вариант: остаток 0, он чётный, Петя идёт в школу. Ирония: единственный способ гарантированно не проспать — не делать домашку вообще (говорят, автор этой задачи был лично знаком с Г. Остером).

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

Программа получает на вход целые числа по одному в строке, по модулю не превышающие 10 000. Последовательность завершается числом 0 (ноль не входит в последовательность и не обрабатывается). Гарантируется, что в последовательности есть хотя бы один элемент, оканчивающийся на 3 в пятеричной системе счисления.

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

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

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

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