Информатика

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

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

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

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

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

Сколько существует программ, которые преобразуют число \(100\) в число \(132\), для которых траектория вычислений содержит число \(115\) и не содержит чисел \(106\) и \(121\)?

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

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

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.

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

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