Информатика

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Массив 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 вида символов в строке должны быть). Определите, какая строка могла быть подана на вход алгоритму?

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