Информатика

Граф — это множество вершин (обозначаются на схемах точками или кругами), некоторые из которых соединены между собой рёбрами (обозначаются на схемах линиями). Бинарным деревом называют такой граф, на который наложен ряд ограничений:

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

Примеры бинарных деревьев (корень показан как вершина с номером 1):

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

Будем называть высотой бинарного дерева максимальное возможное в этом дереве количество рёбер, которое может потребоваться пройти от корня дерева, чтобы добраться до какой-либо вершины графа (при этом нельзя дважды проходить через одно и то же ребро или одну и ту же вершину). На картинках выше изображены бинарные деревья высотой 2.

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

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

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

Назовём полным бинарным деревом высоты h такое бинарное дерево, в которое не может быть добавлена ни одна вершина с ребром так, чтобы высота дерева не увеличилась.

Победителем в игре будет считаться игрок, в чей ход бинарное дерево превратится в полное бинарное дерево высоты 12. Игроки также договорились, что ни в какой момент игры высота дерева не должна стать больше 12. Первым ходит Петя. Кто может победить в такой игре независимо от ходов противника?

В ответ запишите два числа через пробел без кавычек: номер игрока, который может победить независимо от ходов противника (1 — Петя, 2 — Витя) и максимальное количество ходов, которые может потребоваться выполнить этому игроку для победы. Пример записи ответа, если выиграть может Петя своим вторым ходом независимо от ходов противника: «1 2».

Недавно в ИТМО произошли изменения номеров аудиторий, но вот незадача — в вашем расписании остались старые номера. Чтобы получить новые номера аудиторий и попасть на все занятия, вы можете воспользоваться следующей логикой:

Если номер не заканчивается на 0, из него вычитается 50. Затем, независимо от этого, мы всегда уменьшаем номер на 100.

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

Далее, если в номере присутствует цифра 7, это требует особого внимания: в таком случае номер умножается на остаток от деления этого номера на 5, увеличенный на 1. Если цифры 7 нет, номер делится на 3 (целочисленно).

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

Список номеров аудиторий из вашего расписания: 483, 3198, 9801, 1944.

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

Пример ответа: 4 100 200 300

Сколько существует последовательностей из 8 битов, для которых выполняется следующее равенство:

A(X) ИЛИ B(X) = ИСТИНА

Где X — последовательность из 8 битов, т.е. \(X = (x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7)\). A(X), B(X) — логические выражения, заданные следующим образом:

\(A(X) = (x_0 \oplus x_4) \wedge (x_1 \oplus x_5) \wedge (x_2 \oplus x_6) \wedge (x_3 \oplus x_7)\)

\(B(X) = (x_0 \wedge x_1) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3) \vee (x_3 \wedge x_4) \vee (x_4 \wedge x_5) \vee (x_5 \wedge x_6) \vee (x_6 \wedge x_7)\)

Здесь \(\oplus\) обозначает XOR (Исключающее ИЛИ), \(\wedge\) — И (конъюнкцию), \(\vee\) — ИЛИ (дизъюнкцию).

Примечание. Таблица истинности для XOR:

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

В ответе укажите целое число.

Компьютерщик Артур собирает серверный стенд для запуска вычислительного кластера. Стенд имеет размер 2×2×5:

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

• 2 уровня (верхний и нижний),
• на каждом уровне — 2 ряда по 5 слотов.

Всего в стенде 20 слотов. Артуру нужно установить 3 одинаковых мощных GPU-узла. Артур знает, что, если два мощных GPU окажутся слишком близко, система перегреется. Поэтому два GPU-узла не могут находиться в соседних по грани слотах.

Соседними считаются слоты:

• слева или справа в одном ряду,
• спереди или сзади в пределах одного уровня,
• строго над или под друг другом между уровнями.

Расположение по диагонали допустимо. Пример допустимого расположения узлов:

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

Сколькими способами Артур может установить 3 GPU-узла так, чтобы не нарушить правило охлаждения? В ответ укажите единственное число.

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

Для кодирования числа n подбирается такая сумма степеней двойки, чтобы в сумме получилось число n. При этом каждую из степеней двойки можно домножить на любую цифру от 0 (включительно) до 9 (включительно). Таким образом, многие числа можно представить как сумму степеней, домноженных на разные цифры, разными способами, например:

\(39 = 2^5 \cdot 1 + 2^0 \cdot 7 = 2^4 \cdot 2 + 2^0 \cdot 7 = 2^4 \cdot 2 + 2^2 \cdot 1 + 2^0 \cdot 3 = \ldots\)

После того как для числа n подобраны степени двойки и цифры, на которые эти степени домножаются, определяется максимальная степень двойки, которая участвует в сумме, и к этому числу прибавляется «1» — столько разрядов будет в финальном числе, обозначим это количество разрядов как r. Далее разряды закодированного числа нумеруются с 0 и до r−1. На каждую позицию записывается цифра, на которую домножалась соответствующая степень двойки.

Например, если сумма 39 была подобрана как \(2^5 \cdot 1 + 2^0 \cdot 7\), то количество разрядов r = 5+1 = 6, и число записывается в виде 700001. А если сумма 39 была подобрана как \(2^4 \cdot 2 + 2^2 \cdot 1 + 2^0 \cdot 3\), то число будет записано уже в виде 30102.

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

Пример: для числа 2 возможно две записи: \(2 = 2^1 \cdot 1\) (запись 01) и \(2 = 2^0 \cdot 2\) (запись 2). При интерпретации чисел 01 и 2 в десятичной системе получаем суммы цифр 0+1 = 1 и 2, из них минимальна 1, значит в ответ было бы нужно записать «01».

Света и Костя обсуждают новую образовательную программу в переписке. Формулировки важны, а интернет иногда «шалит»: при передаче сообщения один бит может исказиться. Чтобы восстанавливать смысл, они решили кодировать каждый фрагмент сообщения кодом Хэмминга (7,4), который умеет исправлять ровно одну ошибку.

Каждый фрагмент состоит из 4 информационных битов d1 d2 d3 d4. Они кодируются в 7-битное слово, где позиции нумеруются слева направо от 1 до 7:

• позиции 1, 2, 4 — проверочные биты p1, p2, p4;
• позиции 3, 5, 6, 7 — данные d1, d2, d3, d4.

То есть буква имеет вид (индексация с 1):

Позиция	1	2	3	4	5	6	7
Бит	p1	p2	d1	p4	d2	d3	d4

Проверка. Для проверки сначала вычисляются s1, s2, s4 с помощью XOR (Исключающее ИЛИ, обозначается как ⊕):

• s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4 (позиции 1, 3, 5, 7)
• s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4 (позиции 2, 3, 6, 7)
• s4 = p4 ⊕ d2 ⊕ d3 ⊕ d4 (позиции 4, 5, 6, 7)

Далее рассчитывается синдром ошибки S: S = s1·1 + s2·2 + s4·4.

• если S = 0, ошибки нет;
• иначе ошибочен бит в позиции S (его нужно инвертировать: 0→1 или 1→0).

Гарантируется, что в каждом принятом фрагменте либо нет ошибок, либо ровно одна ошибка на фрагмент.

Вам дано закодированное слово (состоит из нескольких фрагментов):

1010101 0111110 1100000 0011001 0110101

В ответ запишите пару чисел «номер фрагмента с ошибкой» и «номер бита с ошибкой в этом фрагменте» (без пробела между этими двумя числами); если таких пар несколько, то запишите эти пары через пробел в том же порядке, в котором фрагменты даны в условии (индексация с 1 как для бита, так и для номера фрагмента).

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

Примечание. Таблица истинности для XOR (Исключающего ИЛИ):

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

Процессор читает инструкции переменной длины и работает в две стадии:

1) Выборка. За 1 такт процессор может считать из памяти ровно 8 байт (даже если какая-то инструкция при этом считается не полностью) и положить их в буфер выборки. Размер буфера выборки — 16 байт.

Буфер выборки работает как циклическая очередь. Если в буфере нет места для новых данных, они записываются поверх старых, уже декодированных данных, начиная с начала буфера, что позволяет не терять последние считанные байты. Точно так же — циклически — происходит последующее чтение данных из буфера. Если в буфере нет места для ещё 8 байт (в буфере уже находится более 8 ещё не декодированных байт), выборка в этот такт не выполняется. Байты поступают в конец буфера и читаются с начала, как в очереди.

2) Декодирование. Инструкции декодируются строго по порядку. Время декодирования зависит от длины инструкции:

• 2 байта = 1 такт
• 4 байта = 2 такта
• 8 байтов = 3 такта

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

Программа состоит из 1000 инструкций: 40% — длиной 2 байта, 30% — длиной 4 байта, 30% — длиной 8 байт.

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

Андрей — студент ИТМО. Он очень любит гулять по Санкт-Петербургу. Город представляет собой граф из \(n\) перекрёстков и \(m\) улиц, по улицам можно ходить в обе стороны.

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

Так как ходить одинаковыми маршрутами слишком скучно, ему стало интересно, можно ли начать в перекрёстке \(v\) и закончить в перекрёстке \(u\), чтобы у прогулки был ритм \(k\).

Маршрут — такая последовательность вершин \(a_1, \dots, a_t\), \(t>1\), что соседние вершины соединены ребром (рёбра и вершины могут повторяться). Длина такого маршрута считается равной \(t-1\).

Вы должны помочь ему и ответить на \(q\) запросов.

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

В первой строке даны числа \(n\) и \(m\) — количество перекрёстков и улиц (\(1 \le n \le 10^5,\ 0 \le m \le 10^5\)). В последующих \(m\) строках дано описание графа, по два числа в строке \(v\) и \(u\) — улица, соединяющая вершины \(v\) и \(u\) (\(1 \le v, u \le n\)). В графе могут присутствовать петли и кратные рёбра. В следующей строке дано число \(q\) — количество вопросов (\(1 \le q \le 10^5\)). В последующих \(q\) строках дано по три числа \(v, u, k\) — стартовый и конечный перекрёсток и требуемая ритмичность прогулки (\(1 \le v, u \le n,\ 1 \le k \le 10^6\)).

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

Выведите \(q\) строк. В \(i\)-й строке — ответ на \(i\)-й запрос: Yes, если существует маршрут с ритмичностью \(k\), и No иначе.

Васе очень нравится игра «2048», но ему не хватает в ней гибкости. Он решил создать свою версию, где размер доски, возможные номиналы плиток и цель игры могут меняться. Ваша задача — написать движок-валидатор для этого турнира.

Игра происходит на квадратном поле размера \( X \times X \) (в данной задаче \( X = 5 \)).

• Слияние. При сдвиге в одном из четырёх направлений плитки с одинаковым номиналом объединяются, если они «налетают» друг на друга. Номинал новой плитки равен сумме двух предыдущих. Одна плитка не может участвовать в слиянии дважды за один ход. Порядок слияния соответствует классической игре 2048. К примеру, строка 22200 при сдвиге вправо превратится в 00024. Под нулём подразумеваются пустые клетки.
• Ход. Считается совершённым, если хотя бы одна плитка изменила своё положение или произошло слияние.
• Очерёдность. После каждого успешного хода на поле должна появиться новая плитка.

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

В первой строке содержится целое число \( n \) (\( 1 \le n \le 10 \)) — количество возможных номиналов новых плиток.

Во второй строке содержатся \( n \) целых различных чисел \( a_1, a_2, \ldots, a_n \) (\( 2 \le a_i \le 2^{10} \)) — доступные номиналы для новых плиток. Гарантируется, что \( a_i \) — степень двойки.

В третьей строке содержится целое число \( m \) (\( 2^{11} \le m \le 2^{20} \)) — минимальная стоимость плитки для победы.

В четвёртой строке содержится целое число \( q \) (\( 2 \le q \le 10^4 \)) — количество запросов.

Далее следуют \( q \) запросов. Каждый запрос начинается с типа операции \( T \). Номер запроса \( x \) считается с нуля.

Типы запросов:

• Тип 1. Вывести текущее состояние доски в виде матрицы \( X \times X \). Пустые клетки выводятся как 0.
• Тип 2 (Появление). На следующей строке даны \( x, y, b \): \( x, y \) — координаты (\( 0 \le x, y < X \)); \( b \) — номинал (\( 2 \le b \le 2^{10} \)).
• Тип 3 (Ход). На следующей строке дано число \( d \) — направление: 0 — вверх, 1 — вправо, 2 — вниз, 3 — влево.

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

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

На каждый запрос первого типа нужно вывести 5 строк по 5 чисел через пробел — доску с плитками. Если плитка пустая, следует вывести 0.

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

Событие	Сообщение
Победа: на поле появилась плитка номиналом не меньше \( m \)	Player won. Step: x
Поражение: нет ни одного хода (тип 3), который сдвинет плитки	Player lost. Step: x
Нарушение очереди: два появления или два хода подряд	Incorrect step. Step: x
Неэффективный ход: ход (тип 3) не изменил состояние доски	Incorrect step. Step: x
Некорректный спавн: клетка занята или номинал недопустим	Incorrect step. Step: x

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

Дана операционная система семейства GNU/Linux. Известны результаты последовательного выполнения нескольких команд в некотором текущем каталоге.

В результате выполнения команды ls -Rl был получен следующий вывод:

В результате выполнения команды cat $(find -type f) 2>/dev/null были последовательно, каждая в своей строке, выведены буквы английского алфавита от a до r.

Известно, что файл с именем file211 содержит символ a, файл с именем file21 содержит символ g, а файл с именем file3 содержит символ r.

Затем были последовательно выполнены ещё три команды:

chmod 222 $(find -type f -regex ".+file.*[13]+")
chmod 664 $(find -type f -regex ".+file.*[23]+1")
cat $(find -type f) 2>/dev/null

Какие символы будут выведены в результате выполнения последней команды? В ответе укажите их подряд без пробелов в алфавитном порядке.

Примечания:

• ls -Rl — команда, рекурсивно выводящая содержимое текущего и всех вложенных каталогов, включая информацию о типе (каталог или регулярный файл) и правах доступа.
• cat $(find -type f) 2>/dev/null — команда, рекурсивно обходящая все подкаталоги и выводящая содержимое всех найденных файлов с игнорированием сообщений об ошибках доступа.
• chmod ### $(find #####) — команда, применяющая маску прав доступа (три восьмеричных числа, соответствующих битам прав на чтение, запись и исполнение для владельца, группы и всех пользователей) для файлов, которые найдёт команда find.
• Ключ -type f у команды find выводит только полные имена регулярных файлов.
• Ключ -regex позволяет выводить только полные имена файлов, соответствующих регулярному выражению.

Специальные символы регулярных выражений: . — любой символ; [] — диапазон допустимых символов (например, [abc]); + — предыдущий символ повторяется 1 или более раз; * — предыдущий символ повторяется 0 или более раз.

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

Маршрутизаторы (аппаратные или программные) выполняют задачу выбора оптимального маршрута 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