Определите две последние цифры шестнадцатеричной записи числа $0,AB_{16}^N$ при $N=20000000038_{10}$.

В ответе запишите подряд две шестнадцатеричные цифры в порядке их следования в числе.

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

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

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

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

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

Рекомендуемое время пояснения решения 2-4 минуты.

Вася хранит фотографию природы формата $3N$ пикселей на $4N$ пикселей. Формат хранения предполагает, что изображение может содержать $65536$ различных цветов, и для хранения каждого пикселя используется одинаковое для всех пикселей минимально возможное количество бит (хранятся только коды пикселей). Вася разработал алгоритм, позволяющий выделить на фотографиях лес, небо и скалы (Вася считает, что фотографировал только их, и его алгоритм относит каждый пиксель к одной из этих категорий). После чего он выяснил, что в фрагментах, определяемых как небо, встречаются всего $2048$ различных цветов, в определяемых как лес – $16384$ различных цвета, а в определяемых как скалы – в $2$ раза меньше, чем в определяемых как небо. Вася изменил формат хранения данных так, чтобы теперь минимально возможное количество пикселей определялось отдельно для леса, отдельно для скал и отдельно для неба (хранятся также только коды пикселей, но пиксели каждого из трех фрагментов кодируются независимо). После обработки его фотография стала занимать на $23400$ Кбайт меньше. Вася считает, что пикселей, относящихся к фрагментам леса, неба и скал на его фотографии поровну. Определите минимальное $N$, при котором это возможно.

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

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

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

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

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

Рекомендуемое время пояснения решения 1-3 минуты.

Дана система логических уравнений. Определите, сколько существует различных наборов переменных $A, B, C$ и $D$, при которых выполняется условие истинности системы.

$\begin{cases} ((A \wedge B) \space XOR \space (B \wedge C)) \space XOR \space (C \wedge D)=1 \\ ((A \lor B) \to (B \lor C)) \to (C \lor D)=1 \\ ((A \lor B) \space XOR \space (B \lor C)) \space XOR \space (C \lor D)=1 \\ ((A \wedge B) \to (B \wedge C)) \to (C \wedge D)=1 \end{cases} \$

Примечание: $\wedge$ - операция конъюнкции, $\lor$ - логическая дизъюнкция, $\to$ - импликация, $\leftarrow$ - обратная импликация, $XOR$ – исключающее или, $1$ – истина. Операция обратной импликации эквивалентна операции $(A \lor \overline{B})$.

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

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

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

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

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

Рекомендуемое время пояснения решения 2-4 минуты.

Последовательности символов строятся по следующим правилам:

Исходная последовательность состоит из двух букв: “$AA$”. Далее на каждом шаге берется очередная буква английского алфавита, и пара таких букв добавляется в начало последовательности и после каждой буквы последовательности, полученной на предыдущем шаге. Например, последовательности, получаемые после первых $3$ шагов, будут выглядеть таким образом (третья последовательность разбита на две строки для лучшего восприятия):

1. $BBABBABB$
2. $CCBCCBCCACCBCCBCCACCBCCBCC$
3. $DDCDDCDDBDDCDDCDDBDDCDDCDDADDCDDCDDBDDCDDC$
   $DDBDDCDDCDDADDCDDCDDBDDCDDCDDBDDCDDCDD$

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

Определите, какие буквы стоят в результирующей последовательности на позициях $12$ $148$ $785$ и $2$ $069$ $987$ $672$ $727$, считая от начала строки с $1$. В ответе укажите их подряд в указанном порядке.

Примечание. Порядок следования символов в английском алфавите: $ABCDEFGHIJKLMNOPQRSTUVWXYZ$.

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

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно программированием или использовали электронные таблицы и/или аналитические методы на каком-то этапе решения задачи?

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

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

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

Рекомендуемое время пояснения решения 1-3 минуты.

Дана блок-схема алгоритма. $M$ – массив размера $N - 1$. Операция $A \%B$ означает взятие остатка от деления $A$ на $B$.

Алгоритм последовательно запустили со всеми натуральными значениями $N$ от $100$ до $199$ включительно. Определите, при каком значении $N$ был выведен наименьший результат (назовем его величиной $A$), а при каком – наибольший (назовем его величиной $B$). В случае, если величина $A$ выводилась несколько раз – определите наименьшее из значений $N$, при которых это произошло. В случае, если величина $B$ выводилась несколько раз – определите наибольшее из значений $N$, при которых это произошло. В ответе укажите через пробел $2$ числа – сначала значение $N$ для величины $A$ и затем значение $N$ для величины $B$.

Примечание: $A/B$ означает операцию целочисленного деления $A$ на $B$.

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

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно программированием или использовали электронные таблицы и/или аналитические методы на каком-то этапе решения задачи?

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

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

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

Рекомендуемое время пояснения решения 2-4 минуты.

Маска сети для IPv4 адресации – это $4$-х байтное число, которое делит IP адрес на адрес сети (первая часть) и адрес узла (вторая часть). У всех адресов одной IP-сети совпадают первые части и отличаются вторые. Для части IP адреса, соответствующей адресу сети, в маске сети содержатся двоичные единицы, а для части IP адреса, соответствующей адресу узла, в маске сети содержатся двоичные нули. Для записи масок сетей часто используется нотация, когда после IP-адреса через «$/$» указывается число бит, отводимых в маске под адрес сети. Например, для адреса $11.12.0.8$ и маски $255.0.0.0$ запись будет иметь следующий вид $11.12.0.8/8$. Служебным адресом сети называют адрес, у которого все биты адреса узла (второй части) равны $0$. Широковещательным адресом сети называют адрес, у которого все биты адреса узла (второй части) равны $1$.

Известно, что широковещательный адрес некоторой сети – $192.121.87.255$, а адрес $192.121.83.178$ не принадлежит этой сети. Определите служебный адрес этой сети и ее маску. Если существует несколько возможных масок, укажите ту, у которой максимально количество узлов в сети.

Введите ответ на поставленную задачу в виде: $A.B.C.D/M$, где $A, B, C, D$ – байты служебного адреса сети в десятичной системе счисления, а $M$ – число бит, отводимых под адрес сети.

Пример записи ответа:
11.12.0.8/8

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

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

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

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

Рекомендуемое время пояснения решения 1-3 минуты.

Петя изучает различные виды диаграмм в электронных таблицах. Для того, чтобы потренироваться в построении точечной диаграммы с маркерами, Петя решил изобразить логотип IT-компании VK, заполнив целыми неотрицательными числами диапазон $A2:B21$:

Известно, что числа в столбце $B$ отсортированы по невозрастанию. Какая минимальная сумма может быть у чисел в красных ячейках. В ответе укажите целое число.

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

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

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно в электронных таблицах или использовали программирование и/или аналитические методы на каком-то этапе решения задачи?

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

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

4. Если в какой-то части решения Вы использовали аналитические методы решения, опишите, какие зависимости, закономерности и как Вы определили из условия или результатов вычислений в электронных таблицах, какие данные и формулы использовали для вычислений, и как это позволило получить ответ. Рекомендуемое время пояснения решения 1-3 минуты.

Перед выпуском VK Messenger'а разработчики из IT-компании «VK», как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

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

1. генерируется случайный сценарий взаимодействия пользователей с приложением;
2. в приложении симулируется выполнение этого сценария;
3. проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

1. Первый набор состоит из событий вида «в момент времени $t_i$ поступил запрос регистрации нового пользователя с $\text{ID}$ $\mathtt{id}_i$ и ником $\mathtt{handle}_i$».
   Гарантируется, что $\text{ID}$ уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же $\text{ID}$ может попробовать зарегистрироваться еще раз.

2. Второй набор описывает события вида «в момент времени $t_i$ пользователь с ником $\mathtt{handle}_{i,1}$ отправляет запрос на смену ника на $\mathtt{handle}_{i,2}$».
   Гарантируется, что для каждого такого запроса ник $\mathtt{handle}_{i,1}$ кому-то принадлежит. Если $\mathtt{handle}_{i,2}$ уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.

3. Третий набор описывает события вида «в момент времени $t_i$ пользователь с ником $\mathtt{handle}_{i,1}$ отправляет сообщение пользователю с ником $\mathtt{handle}_{i,2}$».
   Гарантируется, что и $\mathtt{handle}_{i,1}$, и $\mathtt{handle}_{i,2}$ на момент времени $t_i$ соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происходят в одно и то же время, то есть все $t_i$ уникальны.

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

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

В первой строке ввода дано единственное целое число $T$ — количество сценариев, которое вам необходимо обработать ($1 \le T \le 100$).

Далее следуют $T$ описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания $q$-го набора ($q$ от $1$ до $3$) дано единственное целое число $n_q$ — количество событий в наборе, после чего следуют $n_q$ строк в указанном ниже формате ($1 \le n_1 + n_2 + n_3 \le 1000$; $0 \le n_q$).

1. События первого набора задаются в формате «$\text{REG}$ $\mathtt{id}_i$ $\text{BY}$ $\mathtt{handle}_i$ $\text{AT}$ $t_i$».
2. События второго набора задаются в формате « $\text{CHANGE}$ $\mathtt{handle}_{i,1}$ $\text{TO}$ $\mathtt{handle}_{i,2}$ $\text{AT}$ $t_i$».
3. События третьего набора задаются в формате «$\text{SEND FROM}$ $\mathtt{handle}_{i,1}$ $\text{TO}$ $\mathtt{handle}_{i,2}$ $\text{AT}$ $t_i$».

Моменты событий $t_i$ — целые числа от $1$ до $10^9$. Также все $\mathtt{id}_i$ — целые числа от $1$ до $10^9$, а $\mathtt{handle}_i$ — строки из маленьких латинских букв длины не более $10$.

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

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

Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число $q$ — количество зарегистрированных пользователей. В следующих $q$ строках выведите статистику для каждого пользователя в порядке возрастания их $\text{ID}$ в формате «<$\mathtt{id}$> $\text{RECEIVED }$ <$\mathtt{total}$> $\text{TOP}$ <$\mathtt{count}_\mathrm{top}$> $\text{FROM }$ <$\mathtt{id}_\mathrm{top}$>», где $\mathrm{total}$ — суммарное количество полученных пользователем сообщений, $\mathtt{id}_\mathrm{top}$ — $\text{ID}$ пользователя, от которого он получил больше всего сообщений, а $\mathtt{count}_\mathrm{top}$ — само количество сообщений, полученных от пользователя $\mathtt{id}_\mathrm{top}$.

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве $\mathtt{id}_\mathrm{top}$ минимальный из их $\text{ID}$. Если пользователь не получал сообщения, считайте $\mathtt{count}_\mathrm{top}$ равным $0$.

Пример

2

4
REG 1 BY sh AT 10
REG 2 BY sh AT 11
REG 3 BY qwerty AT 12
REG 2 BY shvetz AT 15
2
CHANGE sh TO shvetz AT 13
CHANGE shvetz TO sh AT 18
4
SEND FROM shvetz TO qwerty AT 14
SEND FROM shvetz TO shvetz AT 16
SEND FROM shvetz TO qwerty AT 17
SEND FROM qwerty TO sh AT 19
2
REG 1 BY a AT 10
REG 2 BY b AT 11
4
CHANGE a TO c AT 14
CHANGE b TO a AT 17
CHANGE c TO a AT 20
CHANGE c TO b AT 23
10
SEND FROM a TO b AT 12
SEND FROM b TO a AT 13
SEND FROM b TO c AT 15
SEND FROM b TO c AT 16
SEND FROM a TO c AT 18
SEND FROM a TO c AT 19
SEND FROM c TO a AT 21
SEND FROM a TO c AT 22
SEND FROM a TO b AT 24
SEND FROM a TO b AT 25

2
1 RECEIVED 2 TOP 1 FROM 1
3 RECEIVED 2 TOP 2 FROM 1
2
1 RECEIVED 8 TOP 8 FROM 2
2 RECEIVED 2 TOP 2 FROM 1

Комментарий

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

Рекомендации к пояснению решения задачи (только для участников 10 класса).

В пояснении к решению задачи раскройте следующие вопросы:

1. Кратко опишите алгоритм решения задачи.

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

3. По желанию, можно привести оценку сложности предложенного алгоритма.

Рекомендуемое время пояснения решения 2-4 минуты.

Дан массив $a$ длины $n$. Каждый элемент массива — $-1$, $0$ или $1$. Известно, что $-1$ находятся только строго в правой половине массива, то есть на индексах от $\left\lfloor\dfrac{n + 1}{2}\right\rfloor + 1$ до $n$. Все оставшиеся элементы могут быть равны только $0$ или $1$.

С массивом разрешается выполнять следующие два вида действий:

1. Заплатить две монеты и удалить из массива любое число $a_i$. После такого действия массив $[a_1, a_2, \ldots, a_k]$ превращается в $[a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]$.
2. Заплатить одну монету и заменить два стоящих рядом числа $a_i$ и $a_{i+1}$ на $a_{i+1} + 1$ копию числа $a_i$. То есть, возможны следующие преобразования:

Иными словами, $-1$ можно удалить вместе с предыдущим числом, $0$ можно удалить сам по себе, если он стоит не в начале массива, а $1$ можно заменить на предшествующее ей число.

Определите, какое минимальное число монет требуется заплатить, чтобы превратить данный массив в пустой. Обратите внимание, что ответ всегда существует, потому что можно просто $n$ раз применить первую операцию.

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

В первой строке дано единственное целое число $T$ — количество наборов входных данных ($1 \le T \le 100$). Далее следуют $T$ наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число $n$ — изначальную длину массива. В следующей строке через пробел перечислены целые числа $a_1$, $\ldots$, $a_n$ — элементы массива ($-1 \le a_i \le 1$).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит $10^6$.

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

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

Пример

4
7
1 1 0 0 -1 1 1
5
0 0 0 0 0
11
0 1 0 1 1 0 -1 1 1 0 -1
10
0 1 1 1 1 -1 1 0 1 0

6
6
9
11

Комментарий

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

Рекомендации к пояснению решения задачи (только для участников 10 класса).

В пояснении к решению задачи раскройте следующие вопросы:

1. Кратко опишите алгоритм решения задачи.

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

3. По желанию, можно привести оценку сложности предложенного алгоритма.

Рекомендуемое время пояснения решения 2-4 минуты.