ИТМО

ID 95667. ИТМО-2526. 9 класс. Отель

В старом отеле есть очень длинный коридор из \(n\) комнат. Отель полностью заполнен, и в каждой комнате уже живёт некоторое количество людей.

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

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

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

В первой строке записано целое число \(n\ (1 \le n \le 500000)\) — количество комнат в отеле. Во второй строке записаны \(n\) целых чисел \(a_0, a_1, \ldots, a_{n-1}\), отсортированных по неубыванию — количество человек в каждой комнате. В третьей строке записано целое число \(t\ (1 \le t \le 10000)\) — количество запросов на поиск комнаты. В следующих \(t\) строках записано по одному целому числу \(x\ (x \le 10^9)\) — количество человек в комнате, которую ищет инспектор.

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

Для каждого из \(t\) запросов выведите одно целое число — индекс комнаты (нумерация с нуля), в которой количество человек равно \(x\). Если такой комнаты не существует, выведите −1.

ID 95666. ИТМО-2526. 9 класс. Скобочная последовательность

Петя собрал коллекцию из \(N\) строк, каждая из которых является последовательностью круглых скобок (символы «(» и «)»).

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

Петя просит у вас помощи. Он хочет составить как можно больше пар из данных строк. Для пары строк \((A, B)\) он берёт их в указанном порядке и склеивает в одну строку \(A + B\). Пара считается хорошей, если полученная строка является сбалансированной. Каждая исходная строка может входить не более чем в одну пару. Требуется определить максимальное количество хороших пар, которое можно составить.

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

В первой строке дано целое число \(N\ (1 \le N \le 50000)\) — количество скобочных последовательностей. В каждой из следующих \(N\) строк записана одна скобочная последовательность, состоящая только из символов «(» и «)». Длина каждой последовательности не превосходит 100.

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

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

ID 95665. ИТМО-2526. 9 класс. На первый-второй-третий рассчитайтесь

Прототип процессора имеет 3 уровня кэшей: L1 — самый маленький самый быстрый, L2 — имеет больший объём, но меньшую скорость взаимодействия и L3 — ещё больший объём и ещё меньшая скорость. Данные, которые не удалось поместить в кэш или которые были вытеснены из него, хранятся в оперативной памяти. Для всех уровней кэша существует процедура очистки. Процедура проводится каждые N секунд (N различно для каждого уровня кэша) — в этом случае на уровень ниже перемещаются все данные, которые не были востребованы за последние N секунд, либо в случае недостатка места в кэше — в этом случае фрагменты данных в порядке убывания количества секунд с момента последнего использования (т.е. начиная с тех, что были использованы наиболее давно) перемещаются на уровень ниже до тех пор, пока свободного места не станет достаточно.

В случае, если процессору требуются некоторые данные, он сначала ищет их в кэше L1, затем в L2, затем в L3, затем в RAM. При этом данные перемещаются на уровень выше (для RAM уровнем выше будет кэш L3, для кэша L3 — кэш L2, для кэша L2 — кэш L1), если такое перемещение возможно (размер фрагмента данных не должен превышать размер кэша). Если операции чтения и перемещения должны произойти одновременно, сначала произведётся операция перемещения, затем операция чтения. Количество секунд, необходимых для чтения, округляется вверх до ближайшего целого.

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

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

Ниже представлена таблица с характеристиками кэшей:

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

Определите суммарный объём фрагментов данных в каждом из кэшей после окончания работы в КБайт. В ответ запишите через пробел 3 числа: количество данных в L1, L2 и L3.

ID 95664. ИТМО-2526. 9 класс. Пара ключей

Дана сеть узлов:

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

Проход по ребру между узлами может быть выполнен, если ключ, с которым осуществляется проход, подходит под маску, соответствующую этому ребру. На месте * должны находиться 1 или более символов.

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

1. 6, 153
2. 11, 183
3. 25, 70
4. 42, 27
5. 115, 30

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

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

ID 95663. ИТМО-2526. 9 класс. Отрезки и прямоугольник

Дан набор отрезков, расположенных на прямых y=5 и y=10. Отрезки на y=5 определяются следующим образом: отрезок начинается в точке x=x1 (x1 — натуральное число) и имеет длину 2·x1. Отрезки на прямой y=10 начинаются в точке x2 (x2 — натуральное чётное) и имеют длину x2.

Дан прямоугольник с координатами углов {1000; 1}, {2000; 1}, {2000; 15}, {1000; 15}. Определите, сколько отрезков пересекают этот прямоугольник (то есть начинаются раньше него и заканчиваются позже) и сколько отрезков имеют начало или конец во внутренней области (не включающей в себя границы) данного прямоугольника. В ответе укажите через пробел два искомых числа.

ID 95662. ИТМО-2526. 9 класс. Кто пустил жадин в подземелье?

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

Однако Даня и Аня столкнулись с проблемой: они могут унести с собой только 100 кг добычи. Даня предложил отсортировать список по убыванию ценности и класть в рюкзак самые дорогие предметы, которые может положить. Аня решила, что Даня действует слишком необдуманно и предложила отсортировать список по убыванию цены за килограмм, после чего класть в рюкзак предметы с самым большим соотношением, которые может положить. Помогите Ане проверить свою тактику — вычислите, на сколько монет больше она получит. Если Аня получит меньше монет, чем Даня, укажите отрицательное число.

ID 95661. ИТМО-2526. 9 класс. Точные данные съела собака

В зоопарке продаются 3 типа входных билетов: Детские, Общие и Льготные. Сотрудники зоопарка составили для трёх различных месяцев диаграммы распределения билетов по типам. Однако эти диаграммы были утрачены сотрудниками, и они смогли только приблизительно восстановить по памяти их вид и составили новые диаграммы, с минимальной используемой долей в 1/8 круга, а не в 1%.

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

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

ID 95660. ИТМО-2526. 9 класс. True? True!

Дан фрагмент электронной таблицы в режиме отображения формул. В ячейку A1 поместили некоторое натуральное число.

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

Формулу из ячейки A3 скопировали во все ячейки диапазона A4:A32, формулы из ячеек B2, C2 и D2 скопировали во все ячейки диапазонов B3:B32, C3:C32 и D3:D32 соответственно. Определите наименьшее возможное значение в ячейке A1, если известно, что в столбике C оказалось ровно 7 единиц и 13 двоек.

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

ID 95659. ИТМО-2526. 9 класс. Три сита

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

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

Определите, какое минимальное число N могло быть подано алгоритму на вход, если A = 3, B = 4, C = 3, а на выходе был получен результат 99 300 80.

Примечание: операция A % B означает взятие остатка от целочисленного деления A на B.

ID 95658. ИТМО-2526. 9 класс. Фоторобот подозреваемого

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

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

Массив ANS изначально заполнен нолями. На вход данному алгоритму была подана строка S длины N=15, в результате чего была выведена строка из N чисел: 0 0 0 3 0 0 0 1 0 6 0 0 3 0 0. Известно, что исходная строка S была составлена из символов a, b и c (все 3 вида символов в строке должны быть). Определите, какая строка могла быть подана на вход алгоритму?

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

ID 95657. ИТМО-2526. 9 класс. Альбомная и портретная

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

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

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

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

ID 95656. ИТМО-2526. 9 класс. По таблице

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

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

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

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

ID 95655. ИТМО-2526. 9 класс. Куда уж проще

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

\((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

ID 95654. ИТМО-2526. 9 класс. Зависимые функции

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

\(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 принимает значение ИСТИНА?

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

ID 95653. ИТМО-2526. 9 класс. Фото в багровых тонах

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

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

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

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

ID 95652. ИТМО-2526. 9 класс. Админ-оптимизатор

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

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

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

ID 95651. ИТМО-2526. 9 класс. Рубрика «Эксперименты»

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

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

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

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

ID 95650. ИТМО-2526. 9 класс. Несколько возможных периодов

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

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

ID 95649. ИТМО-2526. 9 класс. Дима и забытая функция

Дима плохо подготовился к тесту по строковым алгоритмам. Он отлично знает, как построить 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\) — длина строки.

ID 95648. ИТМО-2526. 9 класс. Химический парсер

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

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

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

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

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

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

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

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

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

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