Информатика

Дана таблица истинности некоторой логической функции 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) — возвращает длину строки (количество символов в строке).

Вам дана экосистема, в состоянии которой происходят циклические изменения. Она обладает следующими параметрами:

• O — кислород в конце итерации.
• A — количество водорослей типа A в конце итерации.
• B — количество водорослей типа B в конце итерации.
• U — количество улиток в конце итерации.
• K — количество креветок в конце итерации.

После каждой итерации мы записываем новое состояние системы. Состояние системы на каждой итерации меняется по следующим правилам (именно в таком порядке):

1) Водоросли добавляют кислород:

• если O ≤ 25, то \( O_{tmp} = O + 4 \cdot A + 7 \cdot B \);
• если O > 25, то \( O_{tmp} = O + 4 \cdot A \) (водоросли B «не работают»).

\( O_{tmp} \) — это сколько кислорода получилось после работы водорослей на данной итерации, до того как улитки и креветки начали дышать.

2) Улитки и креветки тратят кислород:

\( O_{after} = O_{tmp} - 3 \cdot U - 1 \cdot K \).

\( O_{after} \) — это сколько кислорода осталось в конце итерации после дыхания животных (то есть после того, как улитки и креветки потратили кислород).

3) Проверка условий:

• Если \( O_{after} < 8 \) — креветки погибают, и экосистема не может дальше функционировать.
• Если \( O_{after} > 40 \) — экосистема перенасыщается и не может дальше функционировать.

4) Выбираем ровно одно действие \( d_i \):

• \( d_i = 0 \) — ничего не делать;
• \( d_i = 1 \) — посадить 1 водоросль A (A увеличится на 1);
• \( d_i = 2 \) — посадить 1 водоросль B (B увеличится на 1);
• \( d_i = 3 \) — убрать 1 улитку (можно только если улиток было хотя бы 1).

В конце итерации получаем следующие значения:

• \( O_i = O_{after} \)
• \( K_i = K \)
• \( A_i = A + 1 \) (если \( d_i = 1 \), иначе A)
• \( B_i = B + 1 \) (если \( d_i = 2 \), иначе B)
• \( U_i = U - 1 \) (если \( d_i = 3 \), иначе U)

Вам нужно выбрать действия на каждой итерации. Выбирайте действия так, чтобы экосистема прожила максимальное количество итераций. Итерация i считается прожитой, даже если после проверки условий на этой итерации экосистема перестаёт функционировать. В ответ запишите максимальное количество итераций, которое сможет прожить экосистема.

Стартовые данные: \( O_0 = 31,\ A_0 = 3,\ B_0 = 0,\ U_0 = 7,\ K_0 = 6 \).