Задача A. Attacking rooks ≡

Условие

На шахматной доске стоит пешка в координатах x, y (x — номер вертикали, y — номер горизонтали).

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

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

Входные данные содержат целые числа x и y.

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

Выходные данные должны содержать единственное целое число — максимальное количество ладей.

Ограничения

1 ≤ x, y ≤ 8

Примеры тестов

1 1

8

Задача B. Back from the future ≡

Условие

Коля Герасимов родился 1 января 1970 года. Попав в квартиру странного соседа 11 апреля 1982 года, он обнаруживает в ней машину времени и перемещается ровно на 100 лет в будущее (то есть попадает в 11 апреля 2082 года).

Прожив в будущем ровно a лет, Коля возвращается на той же машине назад в прошлое и живет обычной жизнью, не привлекая к себе особого внимания, собирая ценный для историков будущего архивный материал. Спустя ещё ровно b лет после возвращения, Коля совершает второе и последнее перемещение ровно на 100 лет в будущее. После этого он живет в будущем, не старея (о возможностях медицины времён наших потомков мы можем только мечтать).

Сколько полных лет прожил Коля Герасимов к 1 января n-го года?

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

Входные данные содержат три натуральных числа: a, b и n.

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

Выходные данные должны содержать одно натуральное число — возраст Коли в годах на 1 января указанного года. Если в указанный день Коля отсутствовал в текущем времени — выведите число  − 1.

Ограничения

2 ≤ a + b ≤ 99

1971 ≤ n ≤ 3000

Пояснение к примерам

В обоих примерах Коля прожил в будущем 12 лет, вернулся, и через 27 лет снова отправился в прекрасное далёко. Временная линия жизни Коли приведена на рисунке. К 1 января 2088 года он прожил 18 полных лет. А вот 1 января 1988 года он находился в будущем.

Примеры тестов

12 27 2088

18

12 27 1988

-1

Задача C. Circulation of try-square ≡

Условие

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

Ваша программа должна по координате точки на оси определить, какая часть угольника с ней соприкасалась.

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

Входные данные содержат три натуральных числа a, b и n — длины деревянной и металлической внутренних сторон угольника и координата точки. Гарантируется, что a и b — катеты Пифагорова треугольника (то есть гипотенуза является целым числом).

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

Выход должен содержать одно слово:

• wood, если точка соприкоснется с деревянной ручкой,
• metal, если точка соприкоснется с металлической доской,
• empty, если угольник не коснется точки.

Ограничения

3 ≤ a < b ≤ 1000

1 ≤ n ≤ 10⁹

Примеры тестов

3 4 11

wood

Задача D. Discount season ≡

Условие

Вася узнал, что в магазине, расположенном неподалеку, начался сезон скидок.

За один поход в магазин покупатель пытается приобрести как можно больше товаров с общим весом не более W_max, чтобы иметь возможность унести их с собой. Каждый товар имеется в магазине в единственном экземпляре. По правилам распродажи одному клиенту разрешается совершить не более 3 заходов.

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

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

В начале входных данных указано общее количество товаров n, за которым следует n пар целых чисел: P_i — стоимость i-го товара, W_i — его вес.

Далее во входных данных следует максимальная допустимая стоимость P_max (в сумме за все заходы) и вес W_max, который может унести Вася за один заход.

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

Выходные данные должны содержать оптимальную последовательность покупок, записанную в следующем виде.

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

Если существует несколько оптимальных решений, выведите любое из них.

Ограничения

0 < n ≤ 100, 0 < P_i ≤ P_max ≤ 100, 0 < W_i ≤ W_max ≤ 10

Примеры тестов

12

10 2
10 2
10 8
10 2
5 3
10 2
1 7
10 2
10 4
10 2
1 3
10 2

100 10

3
3 9 10 11
5 0 1 3 5 7
2 4 6

10

4 1
5 2
1 3
8 2
7 1
5 2
8 3
7 1
5 1
6 8

24 8

1
5 0 1 2 4 8

Задача E. Enforcing nine ≡

Условие

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

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

Лидирующие нулевые цифры менять нельзя.

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

Входные данные содержат целое число N — размер массива, за которым следует N целых чисел a_i.

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

Выведите три целых числа: номер элемента, номер цифры, которую нужно заменить, и цифру, на которую делать замену.

Элементы и цифры нумеруются начиная с 0. Цифры нумеруются справа налево.

Гарантируется, что в сумме элементов исходного массива не содержится цифры 9.

Если требуемого изменения не существует, вывести  − 1. Если решений несколько, вывести любое из них.

Ограничения

1 ≤ N ≤ 100000

|a_i| ≤ 10⁹

a_i ≠ 0

Примеры тестов

1
1

0 0 9

3
11 1 31

0 1 6

2
-8 8

-1

Задача F. Fractional multiplication ≡

Условие

Имеется набор из N рациональных дробей, каждая из которых задается своим числителем A_i и знаменателем B_i.

Требуется написать программу, которая выводит:

• 0 — если произведение всех этих дробей дает единицу либо простое число;
• 1 — если это составное целое число;
• 2 — если это дробное число.

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

Входные данные содержит целое число N, за которым следует набор из N пар целых чисел (A_i, B_i).

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

Выходные данные должны содержать единственное число — ответ задачи.

Ограничения

1 ≤ N ≤ 200, 1 ≤ (A_i, B_i) < 2³²

Примеры тестов

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2

Задача G. Geometric similarity ≡

Условие

Имеются два простых (не имеющих самопересечений) многоугольника, каждый из которых задан последовательностью своих n вершин в порядке обхода либо по, либо против часовой стрелки.

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

• изменение длин всех ребер в константное (не нулевое) число раз;
• поворот на 90^∘ в любом направлении относительно некоторой фиксированной точки;
• параллельный перенос;
• смена направления обхода (по часовой стрелке на против часовой и наоборот).

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

Входные данные содержат натуральное число n, за которым следует 2 ⋅ n вершин (сначала вершины первого, а затем — второго многоугольника), записанных в виде пар целых чисел: (x_i, y_i).

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

Выходные данные должны содержать одно целое число: 1, если многоугольники подобны, 0 в противном случае.

Ограничения

Гарантируется, что оба многоугольника являются невырожденными, т.е. имеют площадь строго больше нуля.

При этом все их ребра также имеют ненулевую длину.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 3 ≤ n ≤ 10⁵

Примеры тестов

5
-300 300
-100 500
 200 400
 200 200
-100 100

 250 120
 150 220
  50 120
 100 -30
 200 -30

1

5
 100 200
   0 400
 300 300
 300 100
   0   0

 350 150
 150 320
  50 220
 100   0
 200   0

0

Задача H. Hereditary string ≡

Условие

Васе по наследству от бабушки досталась текстовая строка S. Вася решил поиграть с этой строкой.

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

Ваша программа должна после каждого шага определять, сколько слов (подстрок из подряд идущих не-пробелов) получилось в строке.

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

В первой строке входных данных содержится строка S. Далее следует строка T, задающая последовательность символов, выбираемых Васей.

Строки состоят из цифр, заглавных и строчных букв латинского алфавита.

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

Выходные данные должны содержать последовательность целых чисел N_i — число слов в строке S после i-го шага.

Ограничения

Регистр символов имеет значение, т.е. заглавные и строчные буквы различны между собой.

1 ≤ |S| ≤ 10⁷, 1 ≤ |T| ≤ 10⁴

Примеры тестов

1a2b3c4d1a2b3c4d
1234abcd

2
4
6
8
6
4
2
0

ababbcc11a2AAcc3
abca1234

3
2
3
4
4
5
4
4

Задача I. Indices symmetry ≡

Условие

Молодой программист Вася разрабатывает хранилище данных, имеющее программный интерфейс многомерного массива. Доступ к элементам в таком массиве осуществляется по их составным индексам: (i₁, i₂, …, i_N). Размерность массива определяется значениями A₁, A₂, …, A_N (то есть 0 ≤ i_k < A_k, k = 1… N).

Диапазоны изменения индексов не убывают (A_k ≤ A_k + 1). Особенностью Васиного массива является индексно-перестановочная симметрия. Это означает, что его элементы, составные индексы которых совпадают с точностью до их перестановки, полагаются тождественными.

Для компактного расположения массива в памяти Вася решил использовать следующую схему. Элементы хранятся последовательно в построчном формате (row-major order) в одномерном массиве, что соответствует лексикографическому возрастанию составных индексов. При этом элементы, для которых некоторая перестановка составного индекса встречалась ранее, пропускаются.

Вашей программе требуется выполнять запросы следующих двух видов.

• По заданному составному индексу определить индекс соответствующей ему ячейки в одномерном массиве.
• По заданному одномерному индексу получить соответствующий ему составной индекс.

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

В начале входных данных находится натуральное N — число измерений массива.

Далее следует последовательность из N целых чисел A_j — размеры массива по каждому измерению. За ними следует число M и M описаний запросов, по одному запросу в строке. Запросы могут быть двух видов:

• Символ f, за которым следует N целых чисел (i₁, i₂, …, i_N) — составной индекс.
• Символ b, за которым следует целое число — одномерный индекс.

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

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

Ограничения

Индексация одномерных и составных индексов по каждому измерению начинается с нуля.

0 ≤ i_j < A_j ≤ 100, A_j ≤ A_j + 1, 1 ≤ N ≤ 10, 1 ≤ M ≤ 10⁵

Примеры тестов

5 5 5 5 5 5

8
f 4 4 4 4 4
f 0 1 2 3 4
b 125
f 0 1 1 2 2
f 3 1 4 0 2
b 100
b 49
b 0

125
49
4 4 4 4 4
39
49
1 3 3 3 3
0 1 2 3 4
0 0 0 0 0

5 1 2 3 4 5

8
f 0 1 2 3 4
b 27
f 0 1 0 1 3
b 41
b 1
f 0 1 1 2 3
f 0 0 0 0 0
b 0

41
0 0 2 3 4
16
0 1 2 3 4
0 0 0 0 1
33
0
0 0 0 0 0

Задача J. Just do it! ≡

Условие

Все, что от вас требуется, это вывести все возможные вариации фразы Just do it!, различающиеся лишь регистром отдельных символов (например jUst DO it!).

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

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

Задача K. Kit of circuits ≡

Условие

Необходимо из ∑ni = 1k_i заданных деталей составить такую схему, у которой количество свободных выходов максимально.

Существует n различных типов деталей: каждый тип характеризуется количеством входов (a) и выходов (b). Любые входы можно подключать к любым выходам. Неиспользуемые выходы называются свободными. При подключении детали к схеме нужно обязательно использовать все входы этой детали.

У итоговой схемы должен быть ровно один вход, чтобы можно было подключить схему к источнику с одним выходом.

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

В первой строке входные данные содержат целое число n — количество типов деталей.

В следующих n строках содержится по три целых числа k_i a_i b_i — количество деталей i-го типа и описание этих деталей.

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

Нужно вывести одно целое число: максимальное количество свободных выходов после сборки и подключения схемы к источнику. Итоговая схема может не содержать деталей, тогда свободным будет только выход источника.

Ограничения

0 ≤ n ≤ 10⁶

1 ≤ k, a, b ≤ 10⁶

Примеры тестов

4
1 3 4
2 1 2
1 7 8
1 1 3

6

3
1 3 4
1 5 6
3 7 7

1

Задача L. Limited permutation ≡

Условие

Имеются два целочисленных массива A и B, длиной N каждый.

Требуется получить лексикографически минимальную перестановку массива A, для которой выполняются условия:

A_i ≤ B_i, i = 1, 2, …, N

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

Входные данные содержат целое число N, за которым следует 2 ⋅ N целых чисел: массив A, а затем массив B.

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

Выходные данные должны содержать N целых чисел — полученную перестановку.

Если решения не существует, выведите единственное число  − 1.

Ограничения

0 ≤ A_i, B_i ≤ 10⁹, 1 ≤ N ≤ 2 ⋅ 10⁵

Примеры тестов

5
1 9 3 7 5
9 3 9 1 9

5 3 7 1 9

5
1 9 3 7 5
9 3 3 1 7

-1