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

Операнды арифметического выражения записаны в системе счисления с основанием 29. В записи чисел переменной x обозначена неизвестная цифра из алфавита 29-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 28.
Для найденного x вычислите частное от деления значения арифметического выражения на 28 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.

Значение арифметического выражения записали в системе счисления с основанием 27. Определите в 27-ричной записи числа количество цифр с числовым значением, превышающим 9.

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы. Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.
Сеть задана IP-адресом одного из входящих в неё узлов 191.128.66.83 и сетевой маской 255.192.0.0.
Найдите в данной сети наибольший IP-адрес, который может быть назначен компьютеру. В ответе укажите найденный IP-адрес без разделителей.
Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать: 11122344.

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

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

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

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

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

 

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

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 3 845 627 серийных номеров требуется не менее 11 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

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

Файл к заданию

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

Повтори 2 [Вперёд 14 Налево 270 Назад 12 Направо 90]
Поднять хвост
Вперёд 9 Направо 90 Назад 7 Налево 90
Опустить хвост
Повтори 2 [Вперёд 13 Направо 90 Вперёд 6 Направо 90]

Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченного заданными алгоритмом линиями, включая точки на линиях.

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости 𝐴(𝑥1,𝑦1) и 𝐵(𝑥2,𝑦2) вычисляется по формуле:
\(𝑑(𝐴,𝐵)=\sqrt{(𝑥2-𝑥1)^2+(𝑦2-𝑦1)^2}\).

В файле А хранятся данные о звёздах двух кластеров, где Н=11, W=11 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о звёздах трёх кластеров, где Н=13, W=13 для каждого кластера. Известно, что количество звёзд не превышает 10 000.

Структура хранения информации о звездах в файле Б аналогична файлу А.

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

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

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



 

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

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

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

Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», не менее 3 единиц. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Напишите программу, которая перебирает целые числа, бóльшие 1 125 000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 7 и не равный ни самому числу, ни числу 7.

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

Каждое число и его искомый наименьший делитель записывайте в отдельной строке.

Количество строк в строке для ответа избыточно.

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

Примечание. Цифры, числовое значение которых превышает 9, обозначены латинскими буквами, начиная с буквы A.

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Если найдено несколько значений S, в ответе запишите наименьшее из них.

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

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа - сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

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

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске.
Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы.
Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.
Сеть задана IP-адресом одного из входящих в неё узлов 143.168.72.213 и сетевой маской 255.255.255.240.
Определите наибольший IP-адрес данной сети, который может быть присвоен компьютеру. В ответе укажите найденный IP-адрес без разделителей.
Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать 11122344.

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300425. 
Среди натуральных чисел, меньших 10⁹, найдите числа, удовлетворяющих маске 2*17?3*2 и делящиеся на 2024, у которых сумма цифр – простое число. Запишите в ответе найденные числа в порядке возрастания, справа от каждого числа запишите частное от его деления на 2024.
 

Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ Y встречается не менее 260 раз.
Для выполнения этого задания следует написать программу.
 

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

1.  Вычти 1
2.  Найди целую часть от деления на 2
 
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 13?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
 

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Типовой пример организации данных в файле
 

ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A
1	4	0
2	3	0
3	1	1; 2
4	7	3

 

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

 

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию

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

Если найдено несколько значений S, в ответе запишите наименьшее из них.