Информатика

Положительное вещественное число, меньшее 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 добавили друг друга в список друзей, таблица будет содержать две записи:

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

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

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

Определите, сколько различных пользователей знает пользователь с 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)\) задана таблицей истинности:

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

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

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

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

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

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

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

Про некоторое положительное вещественное число, меньшее 1, известно следующее:

• Если это число умножить на \(2^{100}\), результат окажется целым числом.
• Если это число умножить на 9 и перевести в запись в двоичную систему счисления, окажется, что эта запись числа не содержит значащих нулей.

Сколько существует таких чисел?

В ответе укажите целое число. Если таких чисел не существует или их бесконечно много, укажите в ответе NULL.

Примечание: число \(0.1_2\) содержит значащий ноль.

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

Учёный проводит кластеризацию точек (звёзд). Центр кластера (центроид) — точка кластера, сумма расстояний от которой до остальных точек кластера минимальна. Расстояние:

ρ(A, B) = √( (x₁ − x₂)² + (y₁ − y₂)² )

В файле A — данные о звёздах двух кластеров, в файле B — трёх. В каждой строке: координата x, координата y, характеристика звезды.

Цвет:                  Размер:
G — белый              I   — сверхгигант
J — зелёный            II  — яркий гигант
L — синий              III — гигант
N — оранжевый          IV  — субгигант
Y — красный            V   — карлик
S — голубой            VI  — субкарлик
Z — жёлтый             VII — белый карлик

Значения записаны в характеристике слитно: обозначение цвета, светимость (арабская цифра 1…9) и обозначение размера (римские цифры). Например, Y3III — красный гигант светимости 3.

Для файла A определите центры кластеров и найдите: A₁ — абсциссу центра кластера с наименьшим количеством звёзд светимости 2; A₂ — ординату центра кластера с наибольшим количеством звёзд светимости 2. Для файла B найдите: B₁ — расстояние между центрами кластеров с минимальным и максимальным количеством красных звёзд (цвет Y); B₂ — наибольшее расстояние между центром кластера и красной звездой из этого же кластера.

В ответе запишите четыре числа: целые части произведений A₁×10000, A₂×10000, B₁×10000, B₂×10000.

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

ρ(A, B) = √( (x₁ − x₂)² + (y₁ − y₂)² )

В файле A хранятся данные о звёздах двух кластеров (H = 6, W = 4,5). В каждой строке записаны координаты x и y одной звезды. В файле ровно три «лишних» точки (аномалии), которые не относятся ни к одному кластеру и которые учитывать не нужно. Гарантируется, что количество точек во всех кластерах различно.

Определите координаты центра каждого кластера и найдите два числа: P_x — расстояние по оси абсцисс между центрами кластеров, P_y — расстояние по оси ординат между центрами кластеров. В ответе запишите целые части произведений P_x×10000 и P_y×10000.

Учёный проводит кластеризацию множества звёзд по их расположению на карте. Кластер — набор точек, лежащих внутри прямоугольника; центр кластера (центроид) — звезда кластера, сумма расстояний от которой до остальных звёзд кластера минимальна. Расстояние между точками A(x₁, y₁) и B(x₂, y₂):

ρ(A, B) = √( (x₁ − x₂)² + (y₁ − y₂)² )

В файле A — данные о звёздах 2 кластеров, в файле B — о звёздах 3 кластеров. В каждой строке: координата x, координата y, характеристика звезды.

Цвет:                  Размер:
G — белый              I   — сверхгигант
J — зелёный            II  — яркий гигант
L — синий              III — гигант
N — оранжевый          IV  — субгигант
Y — красный            V   — карлик
S — голубой            VI  — субкарлик
Z — жёлтый             VII — белый карлик

Значения записаны в характеристике слитно: обозначение цвета, светимость (арабская цифра 1…9) и обозначение размера (римские цифры). Например, Y3III — красный гигант светимости 3.

Для файла A определите центры кластеров и найдите два числа: A₁ — минимальное расстояние от центра кластера с наименьшим количеством звёзд до красного гиганта (цвет Y, размер III); A₂ — максимальное такое расстояние. Для файла B найдите: B₁ — минимальное расстояние между двумя различными жёлтыми карликами (цвет Z, размер V), расположенными в одном кластере; B₂ — расстояние между центрами кластеров с минимальным и максимальным количеством красных звёзд (цвет Y).

В ответе запишите четыре числа: целые части произведений A₁×10000, A₂×10000, B₁×10000, B₂×10000.

Учёный проводит кластеризацию точек (звёзд). Центр кластера (центроид) — точка кластера, сумма расстояний от которой до остальных точек кластера минимальна. Расстояние:

ρ(A, B) = √( (x₁ − x₂)² + (y₁ − y₂)² )

В файле A — данные о звёздах двух кластеров. В каждой строке: координата x, координата y, характеристика звезды.

Цвет:                  Размер:
G — белый              I   — сверхгигант
J — зелёный            II  — яркий гигант
L — синий              III — гигант
N — оранжевый          IV  — субгигант
Y — красный            V   — карлик
S — голубой            VI  — субкарлик
Z — жёлтый             VII — белый карлик

Значения записаны в характеристике слитно: обозначение цвета, светимость (арабская цифра 1…9) и обозначение размера (римские цифры). Например, Y3III — красный гигант светимости 3.

Определите центры кластеров и найдите два числа: A_x — абсциссу ближайшего к центроиду жёлтого карлика (цвет Z, размер V) в кластере с наибольшим количеством звёзд; A_y — ординату этого же жёлтого карлика. В ответе запишите целые части произведений A_x×10000 и A_y×10000.

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

Формат входных данных. В первой строке — два натуральных числа: N (количество строк) и K (вместимость памяти сервера в Кб). Каждая из следующих N строк содержит время регистрации в формате ЧЧ:ММ:СС, идентификатор клиентского устройства и объём данных запроса S (в Кб).

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

Входной файл содержит информацию о заявках граждан в многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма (в минутах от начала суток). Окна специалистов пронумерованы натуральными числами начиная с 1. Приём ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту, начиная со следующей минуты после завершения предыдущего приёма. Если в момент обращения свободных специалистов нет, гражданин уходит. Если в одну и ту же минуту обращается несколько граждан, они рассматриваются по очереди: первым — тот, у кого приём заканчивается раньше.

Формат входных данных. В первой строке — число K (K ≤ 1000) окон. Во второй строке — число N (N ≤ 10 000) граждан. Каждая из следующих N строк содержит два натуральных числа (≤ 1440): время начала и время окончания приёма. Заявки перечислены в произвольном порядке.

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

Напишите программу, которая перебирает целые числа, бо́льшие 4 501 347 296, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей (не обязательно различных), каждый из которых содержит ровно один раз в своей записи последовательность цифр «53».

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

Напишите программу, которая перебирает целые числа, бо́льшие 1 103 285 717, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей (не обязательно различных), каждый из которых содержит ровно один раз в своей записи последовательность цифр «16».

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

Напишите программу, которая перебирает целые числа, бо́льшие 7 513 048, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей (не обязательно различных), каждый из которых содержит в своей записи хотя бы одну цифру 1 и хотя бы одну цифру 6.

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