Олимпиады

Маршрутизаторы (аппаратные или программные) выполняют задачу выбора оптимального маршрута IP-пакета и его отправки по этому маршруту. Для принятия решения анализируется адрес получателя и на основе таблиц маршрутизации устанавливается маршрут.

В таблице маршрутизации присутствуют как минимум следующие поля: адрес назначения (IP-адрес сети или конкретного хоста); идентификатор порта, через который пакет идёт до сети назначения; шлюз (gate). Запись по умолчанию отличается тем, что адрес назначения и маска назначения имеют значения, равные 0.0.0.0.

Пятеро друзей часто заходят в один и тот же компьютерный клуб и знают настройки IP для тех компьютеров, за которыми они обычно сидят:

• PC0: address 172.18.19.34/29, gate 172.18.19.33;
• PC1: address 172.18.19.2/29, gate 172.18.19.1;
• PC2: address 172.18.19.10/29, gate 172.18.19.9;
• PC3: address 172.18.19.18/29, gate 172.18.19.17;
• PC4: address 172.18.19.26/29, gate 172.18.19.25.

Им известна общая схема сети, приведённая на рисунке:

Также они смогли получить таблицы маршрутизации некоторых маршрутизаторов.

Таблица A:

IP назначения	Маска назначения	Порт	Шлюз
172.18.19.8	255.255.255.248	10.244.135.182	10.244.135.186
172.18.19.32	255.255.255.248	10.244.133.122	10.244.133.163
172.18.19.16	255.255.255.240	10.244.133.122	10.244.133.163

Таблица B:

IP назначения	Маска назначения	Порт	Шлюз
172.18.19.32	255.255.255.248	10.244.219.99	10.244.219.5
172.18.19.16	255.255.255.248	10.244.13.76	10.244.13.100
172.18.19.24	255.255.255.248	10.244.13.76	10.244.13.100
172.18.19.0	255.255.255.248	10.244.135.186	10.244.135.182

Таблица C:

IP назначения	Маска назначения	Порт	Шлюз
172.18.19.32	255.255.255.248	10.244.145.115	10.244.145.110
172.18.19.0	255.255.255.248	10.244.145.115	10.244.145.110
172.18.19.8	255.255.255.248	10.244.13.100	10.244.13.76
172.18.19.24	255.255.255.248	10.244.6.247	10.244.6.118

Таблица D:

IP назначения	Маска назначения	Порт	Шлюз
172.18.19.16	255.255.255.248	10.244.6.118	10.244.6.247
172.18.19.8	255.255.255.248	10.244.6.118	10.244.6.247
0.0.0.0	0.0.0.0	10.244.110.121	10.244.110.125

Также они установили, что любой маршрут проходит максимум через три маршрутизатора.

По полученным данным восстановите значения IP-адресов на трёх пронумерованных на схеме портах маршрутизаторов. В ответ приведите IP-адреса для порта 1, 2 и 3 в указанном порядке через пробел.

Известно, что некоторое изображение состояло из 6 различных цветов. Ниже приведены значения цветовых каналов этих цветов в модели RGB.

Цвет	R	G	B
Цвет 1	90	60	90
Цвет 2	60	30	90
Цвет 3	60	60	240
Цвет 4	30	180	30
Цвет 5	30	90	60
Цвет 6	180	90	90

Изображение было переведено в модель HSB, после чего к изображению были применены ровно 3 из следующих преобразований:

• Увеличить Hue на 100;
• Уменьшить Hue на 100;
• Уменьшить Hue в 2 раза;
• Увеличить Hue в 2 раза;
• Увеличить Saturation на 50;
• Уменьшить Saturation на 50;
• Увеличить Brightness на 25;
• Уменьшить Brightness на 25.

Если при применении операций 1–4 получается величина, меньшая 0 или большая 359, она берётся по модулю 360. Если при выполнении операций 5–8 получается величина, большая 100, она принимается равной 100, а если получается величина меньше 0, она принимается равной 0.

Полученное изображение было переведено обратно в модель RGB. После этого в изображении присутствуют следующие цвета:

Цвет	R	G	B
Цвет А	22	21	26
Цвет Б	26	22	21
Цвет В	26	26	26
Цвет Г	79	91	117
Цвет Д	117	117	117
Цвет Е	176	132	147

Определите, какие цвета соответствовали цветам А–Е. В ответ запишите последовательность из 6 цифр без пробелов и разделяющих символов.

Пример записи ответа: 123654

Примечание: для перевода RGB в HSB необходимо выполнить следующие шаги:

• Разделить значения \(R, G, B\) на 255. Полученные значения назовём \(R'', G'', B''\).
• Вычислить величины \(MAX=\max(R'',G'',B'')\), \(MIN=\min(R'',G'',B'')\), \(D=MAX-MIN\).
• \(Br = MAX \times 100\%\)
• \(Sat = \frac{D}{MAX} \times 100\%\) (если \(MAX=0\), \(Sat\) также принимается равным 0).
• Если \(D=0\), \(Hue\) принимается равным \(0^\circ\).
• Если \(MAX=R''\), \(Hue=60^\circ \times \left(\frac{G''-B''}{D} \bmod 6\right)\).
• Если \(MAX=G''\), \(Hue=60^\circ \times \left(\frac{B''-R''}{D} + 2\right)\).
• Если \(MAX=B''\), \(Hue=60^\circ \times \left(\frac{R''-G''}{D} + 4\right)\).
• Если выполняется несколько из условий выше, можно выбрать любое.
• Если в результате вычислений \(Hue<0^\circ\), прибавить к получившемуся значению \(360^\circ\).

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

Для удобства Максим собрал всю имеющуюся информацию в базу данных, которая имеет следующую структуру:

- Таблица competency хранит компетенции, которые может освоить студент в ходе изучения различных дисциплин:

• competency_id — уникальный идентификатор компетенции;
• code — уникальный код компетенции;
• name — название компетенции;
• description — описание компетенции;

- Таблица discipline хранит информацию о дисциплинах, которые студент может изучать при освоении образовательных программ:

• discipline_id — уникальный идентификатор дисциплины;
• code — уникальный код дисциплины;
• name — название дисциплины;
• description — описание дисциплины;

- Таблица program хранит информацию о программах, которые реализуются в университете:

• program_id — уникальный идентификатор программы;
• code — уникальный код программы;
• name — название программы;
• description — описание программы;

- Таблица discipline_competency хранит связку дисциплины и компетенции:

• discipline_id — уникальный идентификатор дисциплины;
• competency_id — уникальный идентификатор компетенции;
• Таблица program_discipline хранит связку дисциплины и образовательной программы:
• discipline_id — уникальный идентификатор дисциплины;
• program_id — уникальный идентификатор дисциплины.

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

В целях оптимизации учебного процесса Максиму поручили определить количество различных пар дисциплин, которые дают как минимум одну одинаковую компетенцию и при этом реализуются в рамках образовательной программы «Микросервисные системы». При этом пары, которые отличаются только порядком элементов, считаются за одну. Если в образовательной программе есть три дисциплины, которые реализуют одну и ту же компетенцию, эти дисциплины образуют три пары (1 и 2, 2 и 3, 1 и 3).
Максим справился достаточно быстро и ушёл на обед. А сможете ли вы проверить, справился Максим с задачей правильно или нет? Определите, сколько пар дисциплин он должен был получить. В ответе введите целое положительное число.

Примечание: файл с базой данных доступен в прикреплённых материалах.

Пример ввода ответа: 17

В ячейках A2:A1001 в порядке возрастания записаны целые числа от 0 до 999.

На рисунке ниже изображён фрагмент электронной таблицы в режиме отображения формул:

(тут должно быть изображение)

Формулу из ячейки B2 скопировали во все ячейки диапазона B2:B1001. В ячейках B1 и C1 записаны целые положительные числа.

По полученным данным построили график, где значения по оси абсцисс берутся из диапазона A2:A2000, а по оси ординат — из диапазона B2:B2000. График изображён ниже:

(тут должно быть изображение)

Какие числа записаны в ячейках B1 и C1? В ответ запишите два числа через пробел, сначала число в B1, затем в C1.

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

Известно, что при запуске алгоритма в качестве значения параметра \(A\) было передано число 6104798700. Какое число было передано в качестве параметра \(B\) при запуске алгоритма, если он вернул массив \([816, -751, 701]\)? В ответе введите одно целое положительное число. Если таких чисел несколько, выберите наименьшее.

Пример ввода ответа: 171717

Дана строка 132465. К ней применяется следующая последовательность преобразований:

• \(N\) символов в середине строки удваиваются. Например, при \(N=1\) строка abc превращается в строку abbc, а строка abcd при \(N=2\) — в строку abcbcd. В случае несовпадения чётности длины строки с чётностью \(N\) данное преобразование пропускается.
• \(N\) символов в конце строки удваиваются. Например, при \(N=1\) строка abc превращается в строку abcc.
• \(N\) символов в начале строки удваиваются. Например, при \(N=1\) строка abc превращается в строку aabc.
• \(N\) увеличивается на 2.

Данная последовательность преобразований была применена к строке 15 раз. Определите, какие символы будут в строке в позициях с индексами 100, 200, 300, 400, 500 и 600, если символы строки нумеруются с 0, а начальное значение \(N=4\)? В ответе укажите подряд без пробелов 6 цифр — цифры на искомых позициях.

Пример записи ответа: 123456

Дана логическая схема:

В ней используется вентиль Фредкина, который выглядит следующим образом:

Этот вентиль принимает на вход три бита и отдаёт на выход три бита. Таблица истинности вентиля выглядит следующим образом:

x1	x2	x3	y1	y2	y3
0	0	0	0	0	0
0	0	1	0	0	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	0	0
1	0	1	1	1	0
1	1	0	1	0	1
1	1	1	1	1	1

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

Пример записи ответа: 171717

Дано логическое выражение, записанное в следующей форме:

\(\oplus \land (\oplus X \oplus X ... \oplus XX) (\land A \land B C) \oplus X \oplus X ... \oplus XX\)

Здесь знаком \(\oplus\) обозначается операция «исключающее ИЛИ».

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

Например, выражение \(\land \lor S T P\) в заданной форме записи будет преобразовано к стандартной форме следующим образом: \(\land \lor S T P = \land (\lor S T) P = (S \lor T) \land P\).

В приведённом выражении на месте первого многоточия ⊕X повторяется 2026 раз (с учётом трёх выписанных повторений), на месте второго многоточия — 4051 раз (также с учётом трёх выписанных повторений).

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

Примечание: переменные вводятся большими латинскими буквами; логические операции обозначаются, соответственно, not, and и or. Скобки используются только для изменения порядка выполнения операций. Если порядок выполнения операций очевиден из их приоритетов, дополнительное использование скобок считается ошибкой. Пробелы ставятся между логическими операциями и переменными. Если ответ равен константе, нужно ввести 0, если выражение эквивалентно значению FALSE, или 1, если выражению TRUE.

Пример записи ответа: (A or not B) and C

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

Размер кадра в видео составляет 2560×1440 пикселей, каждый пиксель может быть одного из 65536 цветов, для каждого пикселя в кадре хранится значение его цвета, закодированное с использованием минимального, одинакового для всех цветов количества бит. Частота кадров в видео — 120 кадров/с.

Илье стало интересно, на сколько меньше КБайт памяти займёт видео длиной \(X\) секунд, если центральная (foveal) область будет составлять 10% изображения и к ней не будет применяться сжатие вовсе, радиус внешней границы области вокруг центральной (blend) будет в 2 раза больше радиуса центральной области и вместо хранения цвета каждого пикселя будет храниться цвет каждого второго пикселя. Для остальной части изображения (peripheral) вместо хранения цвета каждого пикселя будет храниться цвет каждого четвёртого пикселя.

Выяснилось, что искомое видео стало занимать на 5184000 Кбайт меньше. При каком наименьшем \(X\) это возможно? В качестве ответа укажите одно целое число.

Пример записи ответа: 171717

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

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

Примеры записи ответа: 3.14, 3,14

Положительное вещественное число, меньшее 1, при записи в восьмеричной системе счисления имеет 999 значимых разрядов после запятой, при этом используются только три цифры: 1, 3 и 4. Каждая цифра встречается минимум один раз, при этом порядок цифр неизвестен. Какая минимальная сумма цифр может быть у записи этого же числа в шестнадцатеричной системе счисления? В ответе укажите целое число в десятичной системе счисления.

Пример записи ответа: 171717

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

Определена следующая последовательность операций:

3. Полученное на предыдущей итерации число переводится в двоичную систему счисления.
4. Получившаяся запись числа циклически сдвигается вправо на один разряд (младший разряд исходного числа становится старшим разрядом нового числа).
5. Новое число переводится в шестнадцатеричную систему счисления.

Если после какой-то операции появляются ведущие нули, они сохраняются.

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

Пример записи ответа: 0A

Андрею на день рождения подарили две очень интересные вещи: лабиринт и лазер. Лабиринт представляет собой матрицу из \(n\) строк и \(m\) столбцов. В матрице могут встречаться пустые клетки ., стены #, а также два типа зеркал: / и \.

После этого Андрей начинает запускать лазер из различных точек лабиринта. Когда луч оказывается в некоторой клетке, происходит следующее:

• если луч находится в пустой клетке, то он продолжает двигаться в том же направлении;
• если луч находится в клетке с зеркалом /, то направление меняется: вверх → вправо; вправо → вверх; вниз → влево; влево → вниз;
• если луч находится в клетке с зеркалом \, то направление меняется: вверх → влево; влево → вверх; вниз → вправо; вправо → вниз.

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

Вам необходимо ответить на \(q\) запросов. В каждом запросе заданы клетка \((x,y)\) и начальное направление луча. Для каждого запроса требуется определить количество переходов между соседними клетками, которое совершит луч до остановки, либо вывести \(-1\), если луч будет двигаться бесконечно (попадёт в цикл).

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

В первой строке даны два целых числа \(n\) и \(m\) — количество строк и столбцов (\(1 \le n, m \le 500\)). В следующих \(n\) строках дано по \(m\) символов — описание матрицы (каждый символ — один из ., #, /, \). В следующей строке дано целое число \(q\) — количество запросов (\(1 \le q \le 10^5\)). В следующих \(q\) строках дано описание запросов вида \(x\ y\ dir\) (\(1 \le x \le n,\ 1 \le y \le m,\ dir \in \{left, right, up, down\}\)). Гарантируется, что клетка \((x,y)\) не является стеной.

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

Для каждого запроса выведите одно целое число в отдельной строке: количество переходов между соседними клетками, либо \(-1\), если луч движется бесконечно. Обратите внимание, что если луч несколько раз посещает одну и ту же клетку, но с разными направлениями, то это считаются разными состояниями.

Глеб решил изучить новый для себя язык программирования. Так как C++ показался ему слишком простым, он выбрал язык Bassembly. Язык этот пока молодой, поэтому найти удалось только его документацию.

Доступные регистры на данном языке: eax, ecx, edx, esi и edi. Каждый регистр хранит беззнаковое 32-битное целое число. Все арифметические операции над регистрами выполняются по модулю \(2^{32}\): при переполнении старшие биты отбрасываются. Например, число \(2^{32}\) эквивалентно 0, а число \(-1\) эквивалентно \(2^{32}-1\).

Bassembly поддерживает пять команд: add, sub, mul, inc, print. Обозначим через reg, reg1, reg2 произвольные регистры из списка выше, а через const — неотрицательное целое число от 0 до \(2^{32}-1\).

Команда add (несколько форм):

• add 0 const — выполнить операцию eax += const.
• add 1 reg — выполнить операцию eax += reg.
• add 2 reg1 reg2 — выполнить операцию reg1 += reg2.

Команда sub (несколько форм):

• sub 0 const — выполнить операцию eax -= const.
• sub 1 reg — выполнить операцию eax -= reg.
• sub 2 reg1 reg2 — выполнить операцию reg1 -= reg2.

Команда mul (две формы):

• mul 1 reg1 — вычислить произведение eax * reg1 и сохранить его в пару регистров [ecx:eax].
• mul 2 reg1 reg2 — вычислить произведение reg1 * reg2 и сохранить его в пару регистров [ecx:eax].

Здесь запись [ecx:eax] обозначает 64-битное число, у которого старшие 32 бита записываются в ecx, а младшие 32 бита — в eax.

Команда inc: inc reg выполняет операцию reg += 1. Команда print: print reg выводит текущее значение регистра reg. Все регистры в начале выполнения программы равны 0.

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

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

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

В первой строке дано одно число \(n\) — количество команд (\(1 \le n \le 10^5\)). В следующих \(n\) строках содержится описание программы, по одной строке на каждую команду. Строки нумеруются от 1 до \(n\).

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

Если в программе встречается ошибочная строка, необходимо вывести все значения, напечатанные командами print до первой ошибки, по одному в строке, а после этого в отдельной строке — номер первой ошибочной строки. Если ошибочных строк нет, вывести все значения, напечатанные командами print, по одному в строке.

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

Исследователь собрал социальный граф для некоторых пользователей социальной сети Y. Этот граф хранится в виде одной таблицы friends со следующими полями:

• first_user_id — целое положительное число, идентификатор первого пользователя;
• second_user_id — целое положительное число, идентификатор второго пользователя.

При этом пара полей (first_user_id, second_user_id) является первичным ключом. Каждая такая пара для удобства хранится дважды. Например, если пользователи с ID 1 и 2 добавили друг друга в список друзей, таблица будет содержать две записи:

first_user_id	second_user_id
1	2
2	1

Исследователь даёт несколько гарантий:

• дружба между двумя пользователями всегда хранится двумя строками;
• нет ситуаций, когда пользователь добавил в список друзей самого себя.

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

Определите, сколько различных пользователей знает пользователь с ID 10 через одно рукопожатие. Обратите внимание, что самого пользователя и его прямых друзей считать не нужно. В ответе введите одно целое неотрицательное число. Если пользователь с указанным ID не встречается в таблице, введите 0.

Примечание: файл с базой данных доступен в прикреплённых файлах.

Пример ввода ответа: 17

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

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

• RTT (Round-Trip Time) — номинальное время полного пути пакета, то есть интервал между отправкой сегмента TCP и получением соответствующего ACK (подтверждения). В течение времени, равного RTT, отправитель может отправить большое количество пакетов, не дожидаясь ACK.
• cwnd (Congestion Window) — окно перегрузки, переменная на стороне отправителя, определяющая максимальное количество неподтверждённых сегментов, которое можно отправить в сеть без ACK.
• MSS (Maximum Segment Size) — максимальный размер полезной нагрузки TCP-сегмента (обычно 1460 байт для Ethernet); используется как единица для роста cwnd.
• ssthresh (Slow Start Threshold) — пороговое значение окна перегрузки; разделяет фазы медленного старта и предотвращения перегрузки. В Tahoe изначально ssthresh не задаётся фиксированно (принимается равным бесконечности), а устанавливается динамически при первой потере. Будем считать, что при первой потере ssthresh = cwnd/2.
• Slow Start — фаза, где cwnd удваивается каждый RTT (при начальном значении, равном 1 MSS), чтобы быстро «нащупать» реальную пропускную способность сети.
• Congestion Avoidance — фаза, наступающая после достижения ssthresh. В этой фазе cwnd растёт линейно (+1 MSS за RTT).

Сначала скорость передачи растёт согласно Slow Start, а как случается первая потеря, рассчитывается ssthresh, после чего cwnd сбрасывается в 1 MSS, заново запускается Slow Start (cwnd удваивается каждый RTT), но уже до установленного ssthresh. Достигнув ssthresh, алгоритм переходит в режим Congestion Avoidance, при котором рост cwnd +1 MSS за RTT, пока не произойдёт новая потеря, после чего ssthresh уменьшается вдвое снова. Это создаёт «зубчатую» кривую cwnd.

Пусть файл из 64 сегментов (по 1460 байт) передаётся по сети с RTT = 120 мс. Используется алгоритм TCP Tahoe.

• Slow Start: cwnd удваивается каждый RTT, начиная с 1 MSS.
• После потери: ssthresh = cwnd / 2, cwnd = 1 MSS.
• Достигнув ssthresh, переход к Congestion Avoidance (+1 MSS/RTT).
• Потеря происходит при cwnd = 16 MSS.

Найдите общее время передачи всех 64 сегментов в миллисекундах. Выберите наиболее близкий к полученному значению вариант ответа: 590, 840, 1150, 1430, 1710, 1990, 2160, 2270, 2400, 2550.

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

В качестве \(t\) Аксель вводит массив, содержащий битовую последовательность из \(2^{32}\) нулей. Нумерация элементов массива начинается с нуля.

Определите, какая последовательность из 8 бит будет находиться, начиная с индекса 4294967124 (4294967124, 4294967125, …, 4294967131). В ответ введите последовательность бит в порядке возрастания их индексов в последовательности без пробелов.

Пример ввода ответа: 01010101

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

• Выяснить номер этой буквы в алфавите (Вася пронумеровал буквы от 1 до 26).
• Выяснить номер в алфавите \(i\)-й буквы ключа.
• Перемножить два данных числа — это и есть Васин код для буквы текста.
• Увеличить \(i\) на 1 и взять по модулю длины ключа.

Исходно \(i=0\), а нумерация букв в ключе и в тексте для шифрования начинается с нуля.

Чтобы проверить свой алгоритм, Вася взял фразу «the quick brown fox jumps over the lazy dog», убрал из неё пробелы, повторил её 15 раз подряд и зашифровал полученный текст.

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

Пример ввода ответа: abcdef

Обозначим за \(X\) некоторое натуральное число, записанное с помощью \(n+1\) бит, т.е. \(X=(x_n x_{n-1} \dots x_0)_2\). Например, если \(n=3\) и \(X=0101_2\), то \(x_3=0, x_2=1, x_1=0, x_0=1\).

Даны логические функции \(A(X)\) и \(B(X)\):

\(A(X)=\bigwedge\limits_{i=0}^{n-1}(x_i \to x_{i+1}) \wedge (x_n \to x_0)\)

\(B(X)=\bigvee\limits_{i=0}^{\left\lfloor \frac{n-1}{2} \right\rfloor} \neg\left( M\!\left(x_i, x_{i+\left\lceil \frac{n+1}{2} \right\rceil}, 1\right) \equiv M\!\left(x_i, x_{i+\left\lceil \frac{n+1}{2} \right\rceil}, 0\right)\right)\)

Здесь \(\lfloor a \rfloor\) — значение \(a\) с округлением вниз, \(\lceil a \rceil\) — значение \(a\) с округлением вверх.

Функция \(M(a,b,c)\) задана таблицей истинности:

a	b	c	M(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Сколько существует чисел \(X\) таких, что \(A(X)=B(X)\), если \(n=19\)? В ответе введите целое положительное число.

Примечание: битовая последовательность может начинаться с нуля.

Пример ввода ответа: 17

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

Вася обратил внимание на такую особенность робота Пети — любая его программа всегда имеет количество команд, кратное 128. Он предложил рассматривать программу робота как последовательность подпрограмм длиной 128 команд, кодируя каждую такую подпрограмму минимально возможным, одинаковым для всех возможных подпрограмм количеством бит.

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

Пример ввода ответа: 512