Информатика

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Поменять местами цифры сотен и десятков

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде сотен меньше цифры в разряде десятков, и меняет эти две цифры местами (например, число 129 превратится в 219, а к числу 210 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 3 и 4 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(120\) в число \(330\), для которых траектория вычислений содержит число \(234\) и не содержит чисел \(133\) и \(317\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 2
2. Прибавить к числу его последнюю цифру

Первая команда увеличивает число на экране на 2. Вторая команда применяется только к числу, у которого последняя цифра отлична от нуля, и прибавляет к числу эту последнюю цифру (например, число 23 превратится в 26, а к числу 20 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 4 и 6 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(20\) в число \(50\), для которых траектория вычислений содержит число \(36\) и не содержит чисел \(30\) и \(40\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Прибавить к числу сумму его цифр

Первая команда увеличивает число на экране на 1. Вторая команда прибавляет к числу сумму его цифр (например, число 20 превратится в 22, а 47 — в 58).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 3 и 4 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(20\) в число \(42\), для которых траектория вычислений содержит число \(26\) и не содержит чисел \(23\) и \(32\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Удвоить цифру в разряде единиц

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра единиц равна 1, 2, 3 или 4, и удваивает эту цифру (например, число 22 превратится в 24, число 13 — в 16, а к числу 25 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 3 и 4 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(20\) в число \(40\), для которых траектория вычислений содержит число \(27\) и не содержит чисел \(25\) и \(35\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 2
2. Заменить все цифры «2» на «6»

Первая команда увеличивает число на экране на 2. Вторая команда применяется только к числу, в записи которого есть хотя бы одна цифра «2», и заменяет все такие цифры на «6» (например, число 24 превратится в 64, а 252 — в 656).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 4 и 6 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(20\) в число \(96\), для которых траектория вычислений содержит число \(64\) и не содержит чисел \(54\) и \(84\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Заменить все цифры «1» на «4»

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, в записи которого есть хотя бы одна цифра «1», и заменяет все такие цифры на «4» (например, число 12 превратится в 42, а 121 — в 424).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 3 и 4 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(11\) в число \(88\), для которых траектория вычислений содержит число \(39\) и не содержит чисел \(33\) и \(43\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Поменять местами цифры единиц и десятков

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков меньше цифры в разряде единиц, и меняет эти две цифры местами (например, число 235 превратится в 253, а к числу 220 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд.

Траекторией вычислений программы называется последовательность результатов выполнения всех команд программы. Например, если к числу 2 дважды применить первую команду, траектория вычислений — это числа 3 и 4 (само исходное число в траекторию не входит).

Сколько существует программ, которые преобразуют число \(200\) в число \(280\), для которых траектория вычислений содержит число \(224\) и не содержит чисел \(217\) и \(238\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Поменять местами цифры единиц и сотен

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде сотен меньше цифры в разряде единиц, и меняет эти две цифры местами (например, число 153 превратится в 351, а к числу 350 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(130\) в число \(360\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 3
2. Прибавь 2

Первая команда увеличивает число на экране на 3. Вторая команда применяется только к чётному числу и прибавляет к нему 2 (например, к числу 10 применимы обе команды, а к числу 13 — только первая).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(10\) в число \(34\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Прибавить 10

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков меньше цифры в разряде единиц, и прибавляет к числу 10 (например, число 102 превратится в 112, а к числу 120 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(100\) в число \(130\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Поменять местами цифры сотен и десятков

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде сотен меньше цифры в разряде десятков, и меняет эти две цифры местами (например, число 129 превратится в 219, а к числу 210 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(110\) в число \(240\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 2
2. Прибавить к числу его последнюю цифру

Первая команда увеличивает число на экране на 2. Вторая команда применяется только к числу, у которого последняя цифра отлична от нуля, и прибавляет к числу эту последнюю цифру (например, число 23 превратится в 26, а к числу 20 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(20\) в число \(42\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Прибавить к числу сумму его цифр

Первая команда увеличивает число на экране на 1. Вторая команда прибавляет к числу сумму его цифр (например, число 20 превратится в 22, а 47 — в 58).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(20\) в число \(37\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Удвоить цифру в разряде единиц

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде единиц равна 1, 2, 3 или 4, и удваивает эту цифру (например, число 22 превратится в 24, число 13 — в 16, а к числу 25 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(22\) в число \(44\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 2
2. Заменить все цифры «2» на «6»

Первая команда увеличивает число на экране на 2. Вторая команда применяется только к числу, в десятичной записи которого есть хотя бы одна цифра «2», и заменяет все такие цифры на «6» (например, число 24 превратится в 64, а 252 — в 656).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(24\) в число \(90\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Заменить все цифры «1» на «4»

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, в десятичной записи которого есть хотя бы одна цифра «1», и заменяет все такие цифры на «4» (например, число 12 превратится в 42, а 121 — в 424).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(12\) в число \(77\)?

В ответе запишите одно целое число.

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Поменять местами цифры единиц и десятков

Первая команда увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков меньше цифры в разряде единиц, и меняет эти две цифры местами (например, число 235 превратится в 253, а к числу 220 эту команду применить нельзя).

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют число \(220\) в число \(264\)?

В ответе запишите одно целое число.

В старом отеле есть очень длинный коридор из \(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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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