Информатика

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

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

Ксюша заметила, что распечатанные фотографии идут повторяющейся последовательностью ПААААПАА, где А — альбомная, П — портретная. Сколько раз у Ксюши возникнет ситуация, в которой ей нужно будет воспользоваться пунктом 3 своих правил, если она поместит в альбом 350 фотографий?

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

Дана таблица истинности некоторой логической функции F, зависящей от трёх переменных — X, Y и Z.

Восстановите функцию F и запишите, используя минимальное число операций.

Пример записи ответа: (X or not Y) and Z

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

Упростите логическое выражение или укажите его результат (при его однозначности).

\((A \vee B) \wedge (A \vee C) \vee \overline{(A \vee B)} \wedge (B \vee C)\)

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

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

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

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

\(F(A,B,C) = (A \wedge G(A,B,C) \vee B)\ \mathrm{XOR}\ (G(A,B,C) \to C)\)

и

\(G(A,B,C) = \overline{A} \to (B \to A \wedge C)\)

Сколько существует различных наборов переменных, при которых функция F принимает значение ИСТИНА и функция G принимает значение ИСТИНА?

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

Дано изображение разрешением 1920×1080 с глубиной цвета 9 бит на каждый из трёх цветовых каналов. К нему применяется цветовой фильтр, который влияет на глубину цвета, изменяя значение выбранного цветового канала по следующим правилам:

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

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

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

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

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

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

В мешочке содержатся 5 красных шариков, 12 зелёных и 7 синих. Существует 5 сообщений о результате эксперимента, в каждом из которых доставали шарики из мешочка. Все эксперименты проводились независимо и имели одинаковое начальное состояние, в рамках каждого эксперимента шарики доставали последовательно.

1. Из мешочка достали 3 шарика, они все оказались разных цветов.
2. Из мешочка достали 3 шарика, они все оказались зелёными.
3. Из мешочка достали 3 шарика, два из них оказались одинакового цвета.
4. Из мешочка достали 5 шариков, три случайных шарика положили обратно, оставшиеся два были разных цветов.
5. Из мешочка достали 5 шариков, никакие три из них не были одного цвета.

Расположите номера этих сообщений в порядке возрастания количества информации, содержащегося в каждом сообщении. В ответ запишите последовательность чисел от 1 до 5, не разделяя их пробелами.

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

Сколько существует чисел \(X_2\) (2 — основание системы счисления), таких, что \(0.17_8 < X_2 < 0.89_{12}\) и при этом X является периодической дробью без непериодической части с длиной периода 4? В качестве ответа укажите одно натуральное число — количество таких дробей.

Примечание: в рамках данной задачи будем считать корректными все дроби, которые можно записать, используя период длины 4. Например, хотя дробь \(0{,}(0101)_2\) можно также записать как \(0{,}(01)_2\), мы будем считать такую дробь периодической дробью с периодом 4.

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

Вы давно дружите с Димой и решили помочь ему. Он передал вам листок, на котором написал свою Z-функцию. Помогите ему построить по ней префикс-функцию.

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

В первой строке содержится целое число \(n\ (n \le 10^5)\) — длина Z-функции Димы. Во второй строке содержится сама функция.

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

Выведите полученную префикс-функцию.

Примечание

Префикс-функция строки \(s\) длины \(n\) — это массив \(\pi[0 \ldots n-1]\), где значение \(\pi[i]\) равно длине наибольшего собственного префикса подстроки \(s[0 \ldots i]\), который одновременно является её суффиксом.

Z-функция строки \(s\) длины \(n\) — это массив \(z[0 \ldots n-1]\), где значение \(z[i]\) равно длине наибольшего префикса строки \(s\), совпадающего с подстрокой, начинающейся в позиции \(i\). Считается, что \(z[0] = n\), где \(n\) — длина строки.

Перебирая изобретения великого учёного Д. И. Менделеева, Вы перенеслись в другую вселенную и стали его учеником. Но в один день, когда Менделеев отдыхал под яблоней, от порыва ветра на него свалилось пару яблок, после чего великий учёный забыл, как раскрывать скобки в химических формулах.

В его записях вы вычитали, что в этом мире существуют всего 26 элементов, обозначаются они заглавными буквами латинского алфавита, сами же формулы строятся по следующему принципу:

Формула — последовательность латинских букв, разделённых числами, которые обозначают количество элемента, стоящего перед числом; если же числа нет, то количество элемента равно единице. Пример: H4ZO2 эквивалентно H4O2Z1.

Также в формуле могут стоять скобки, которые показывают, что количество элементов внутри скобок должно быть умножено на число после скобок. Так, H2(O2Z)3 — это то же самое, что и H2O6Z3.

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

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

На ввод подаётся строка, состоящая из латинских символов, скобок и цифр. Строка всегда является правильной формулой.

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

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

Подсказка: для обработки вложенных скобок удобно использовать стек.

Дан фрагмент таблицы в режиме отображения формул:

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

Формулу из ячейки A3 скопировали во все ячейки диапазона A3:A30. Формулу из ячейки B2 поместили во все ячейки диапазона B2:J30. В ячейки B1 и C1 поместили некоторые числа, в результате чего в ячейке A1 отобразилось число 69. Определите, какие числа были помещены в эти ячейки. В качестве ответа укажите через пробел два числа — число из ячейки B1 и число из ячейки C1.

Таблица соответствия имён используемых функций:

Пример ввода ответа: 5 7

Известно, что в некоторой сети зарегистрировано 15 узлов с различными адресами. Некоторые из этих узлов также управляют подсетями.

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

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

Дан алгоритм:

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

На вход данному алгоритму была подана строка A из 16 десятичных цифр, массив B изначально заполнен 0. В результате алгоритм вывел следующий результат:

Восстановите строку A.

Примечание: операция % означает взятие по модулю.

Робот перемещается по полю 10×10 клеток. В свой ход робот может пойти на 1 клетку вверх, вправо, вниз или влево. Известен алгоритм перемещения робота:

• Выполнить ход в заданном направлении, если в этом направлении есть клетка, эта клетка не была посещена роботом и сумма координат этой клетки не кратна X.
• Увеличить число X на 1. Если X = 12, изменить значение X на 2.
• Пометить текущую клетку робота как посещённую (повторная пометка не является ошибкой, если робот пропустил свой ход).
• Определить направление следующего шага согласно таблице:

Если робот не может переместиться в свой ход, он может его пропустить (т.е. не совершать перемещение, выполнив все остальные шаги алгоритма). Однако робот может пропустить максимум 4 хода подряд, иначе он проигрывает. Определите, через сколько перемещений робот проиграет, если начальное значение X = 2 и робот начинает своё движение в клетке с координатами { 3; 7 } и делает первый ход вправо.

Строки и столбцы поля нумеруются с ноля, первая координата соответствует номеру строки, вторая — номеру столбца, координаты { 0; 0 } имеет верхний левый угол, координаты { 9; 9 } — правый нижний.

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

Два набора значений переменных A, B и C называют не эквивалентными, если значение хотя бы одной переменной различается.

Дано логическое выражение. В данном выражении A, B и C — логические переменные, F — функция от этих переменных.

\((((A \to B) \to C) \to ((A \to C) \to B)) \to F\)

Данное логическое выражение истинно при 8 не эквивалентных наборах значений переменных A, B, C, а F — при 7 таких наборах. Определите функцию F, если известно, что функция F содержит все 3 логические переменные и не более чем 3 логические операции. Если таких функций несколько — запишите любую из них.

В ответе запишите формулу, которая содержит логические переменные A, B и C (все 3) и не более чем три логические операции. Если таких функций не существует, запишите в ответ NULL.

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

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

Вася работает в графическом редакторе с поддержкой нескольких слоёв. Графический редактор настроен так, что значения цветов при наложении слоёв (за исключением фона) складываются друг с другом. В этом графическом редакторе Вася создал картину размером 1920×1080 пикселей из трёх пересекающихся цветных прямоугольников (красного, зелёного и синего) на белом фоне и сохранил её в формате True Color (по 8 бит на каждый из 3 цветовых каналов каждого пикселя). Изначально каждый из прямоугольников находился на собственном слое, однако сохранён был именно итоговый результат, полученный после наложения слоёв.

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

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

Примечание: гарантируется, что все 3 прямоугольника имеют ненулевую площадь и все пересечения непусты.

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

Дано число \(A = (a_1 a_2 \ldots a_k)_N\). В данном числе \(a_1 \ldots a_k\) — \(K\) цифр числа, \(N\) — основание системы счисления. Известно, что и каждая из цифр \(a_1 \ldots a_k\), и \(N\), будучи переведёнными в десятичную систему счисления, окажутся равны некоторой степени некоторого числа \(X\) (число \(X\) идентично для всех, степень — различается).

Известно, что все цифры числа различны и записаны по возрастанию, а \(N\) — наименьшее возможное. Определите максимальное количество идущих подряд нолей в числе \(B\), получаемом в результате перевода числа \(A\) в систему счисления с основанием \(X\), если \(K = 1000\).

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

Корнедуд — маг-архивариус Гильдии Каталогов. В его архиве заклинания лежат в каталоге: у каждого заклинания есть значение силы. По уставу архива Корнедуд может просматривать только первые три заклинания от начала каталога — это называется «тройной просмотр». Его работа заключается в проведении некоторого ритуала.

Силы заклинаний:

4, 3, 5, 3, 4, 3, 2, 2, 4, 3, 5, 3, 4, 3, 2, 2, 4, 3, 5, 3, 4, 3, 2, 2, 4, 3, 5, 3, 4, 3, 2, 2

Ритуал выполняется 20 раз:

• Корнедуд смотрит только на первые 3 заклинания.
• Из этих трёх он выбирает самое сильное заклинание. Если максимумов несколько — выбирает то, которое стоит раньше среди этих трёх. Его сила = t. Это заклинание вычёркивается из каталога (удаляется).
• Каталог смещается:
  • если t чётное — циклически сдвигаем вправо на t позиций;
  • если t нечётное — циклически сдвигаем влево на t позиций.

Циклический сдвиг на t позиций означает, что элементы, выходящие за край каталога, возвращаются с другой стороны, сохраняя порядок. Например, для каталога [1, 2, 3, 4, 5] циклический сдвиг влево на 2 позиции даёт [3, 4, 5, 1, 2], а циклический сдвиг вправо на 2 позиции — [4, 5, 1, 2, 3]. После сдвига началом каталога считается первый элемент получившегося списка.

В ответ следует указать единственное число: какая сила будет у двадцатого выбранного заклинания.

В учебной группе M3107 ребята сдают выполненные работы в электронную систему. Работа каждого студента характеризуется тремя числами:

• Score — базовый балл за работу по шкале от 0 до 100 (чем больше, тем лучше). Это то, сколько поставил преподаватель за качество решения без штрафов.
• Delay — опоздание в минутах: если студент сдал вовремя, то Delay = 0; если сдал на 7 минут позже дедлайна (времени сдачи), то Delay = 7.
• Attempts — количество попыток сдачи (сколько раз отправлял решение). Если сдал с первого раза — Attempts = 1. Если пересдавал/перезагружал ещё 2 раза — Attempts = 3.

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

• за каждую минуту опоздания снимается 2 балла;
• за каждую дополнительную попытку (кроме первой) снимается 5 баллов;
• итоговый балл не может быть меньше 0.

Рейтинг строится по следующим правилам:

• больше Final — студент выше в рейтинге;
• если Final одинаковый — выше тот, у кого меньше Delay;
• если и Delay одинаковый — выше тот, у кого меньше Attempts;
• если всё одинаково — сравниваем ID, выше будет тот, у кого ID меньше.

Вам дан список из 10 студентов. Каждый студент описывается строкой из 4 целых чисел, записанных последовательно через пробел: ID, Score, Delay, Attempts.

В ответ запишите первые 5 значений ID в рейтинге (сверху вниз), через пробел.

Дана блок-схема алгоритма:

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

На вход алгоритму дали следующую строку:

• Её длина = 7.
• Состоит только из символов «a» и «b».
• Начинается с символа «a».

Нужно выяснить, какую строку подали на вход, если на выходе мы получили следующий массив arr: [3, 2, 2, 2, 1, 1, 1].

Примечание. Обозначения некоторых операций:

• [k]*n — создаётся массив из n элементов, каждый из которых равен k. Пример: [3]*5 = [3, 3, 3, 3, 3].
• arr[i:j] — берётся подпоследовательность с i-го элемента (включительно) по j-й (не включительно). Для строк — берётся подстрока с i-го символа (включительно) по j-й (не включительно).
• len(s) — возвращает длину строки (количество символов в строке).