Задача A1. Сумма двух чисел ≡

Условие

Вывести сумму двух заданных чисел.

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

На первой строке входного файла находятся два целых числа a и b ( − 10⁹ ≤ a, b ≤ 10⁹).

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

Вашей программе требуется вывести единственное число — сумму заданных чисел a + b.

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

2 3

5

17 -18

-1

Задача AC. Сумма трёх чисел ≡

Условие

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

На первой строке входного файла находятся три числа a и b ( − 10¹⁶ ≤ a, b, c ≤ 10¹⁶).

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

Вашей программе требуется вывести единственное число — сумму заданных чисел a + b + c.

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

2.0 3.0 0

5.0

Задача AD. Сколько селёдок? ≡

Условие

Витя, Петя и Олег решили сходить на рыбалку за селёдками. В море селёдок много и каждая из них весит строго целое количество килограмм. Олег провёл классификацию рыбы и выяснил, что массы селёдок образуют последовательность, заданную следующим образом: x_i = x_i − 1 + i. Минимальный вес селёдки составляет один килограмм. Мальчики взяли с собой ведро, в которое помещается N килограмм рыбы. Разумеется, они хотели бы вернуться домой с полным ведром селёдок.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 5 * 10¹¹

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

3

1

5

3

Задача AE. Единственный канал у пикселя ≡

Условие

Витя, Петя и Олег — программисты. Они решили написать свой графический редактор на библиотеке Qt!

Всё было хорошо до тех пор пока Витю, который написал модуль управления цветом, не забрали в армию. Пете и Олегу осталось всего-навсего включить готовый модуль в работу и дело в шляпе!

Петя и Олег знают, что цвет пикселя обычно кодируется тремя значениями — red, green, blue. Каждый в диапазоне от 0 до 255. Но модуль Вити возвращает цвет пикселя в виде единственного числа. В битах с 0 по 7 включительно отражена интенсивность синего канала. С 8 по 15 зелёного, а с 16 по 23 интенсивность красного.

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

На вход подаётся число, и буква r\g\b — канал, который нужно оставить. Ваша задача получить итоговый цвет в том же формате.

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

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

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

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

Ограничения

0 ≤ n ≤ 16777215

m ∈ {′r′, ′g′, ′b′}

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

6579300 g

25600

Задача AF. Число-ловелас ≡

Условие

Пусть число, в шестнадцатеричной записи которого присутствует комбинация идущих подряд символов "babe", называется числом-ловеласом.

Требуется выяснить, является ли заданное число ловеласом, используя битовые операции.

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

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

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

Выходные данные должны содержать ответ - строку "YES" или "NO"

Ограничения

0 ≤ n ≤ 18446744073709551615

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

0

NO

47806

YES

Задача B1. Двоичный порядок float ≡

Условие

Требуется написать программу, которая считывает вещественное число в переменную типа float и выводит его двоичный порядок по стандарту IEEE-754.

Для поиска порядка необходимо использовать битовые операции.

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

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

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

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

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

2.0

1

0.5

-1

Задача B3. Задача на ветвление 2 ≡

Условие

Даны четыре числа a, b, c, d. Если их сумма - четное число и произведение неотрицательное, то вывести наибольшее из них, если сумма - нечетное число и произведение неотрицательное , то вывести наименьшее из них,если произведение - отрицательное число, то вывести сумму всех четных чисел.

Формат входного файла

Входной файл содержит четыре целых числа

Формат выходного файла

Выходной файл должен содержать одно целое число

Ограничения

 − 1000 ≤ a, b, c, d ≤ 1000

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

1 2 3 4

4

Задача B4. FizzBuzz ≡

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

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

23

25

Buzz

30

FizzBuzz

Задача B5. Среднее арифметическое ≡

Условие

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

Формат входного файла

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

Формат выходного файла

Выходные данные должны содержать единственное число — среднее арифметическое выборки с точностью не менее 3 знаков после запятой.

Ограничения

1 < n < 10⁵

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

3
1 3 5

3

Задача B6. Квадратное уравнение ≡

Условие

Необходимо написать программу, вычисляющую корни квадратного уравнения общего вида, заданного коэффициентами a, b, c.

Формат входного файла

Входной файл содержит три вещественных числа - коэффициенты квадратного уравнения с точностью до четырех знаков после запятой.

Формат выходного файла

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

Ограничения

0 ≤ a, b, c ≤ 1000

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

3 5 2

-0.6667 -1.0000

0 7.245 -5.222

0.7208 0.7208

Задача B9. Массив наоборот ≡

Условие

Во входном файле дан массив целых чисел a₁, a₂, ..., a_N. Требуется вывести этот массив в обратном порядке.

Формат входного файла

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

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100000

 − 10⁹ ≤ a_i ≤ 10⁹

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

4
1 2 3 4

4 3 2 1

6
9 1 3 -2 3 5

5 3 -2 3 1 9

Задача C1. Фибоначчи ≡

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

Формат входного файла

Входной файл содержит одно целое неотрицательное число N.

Формат выходного файла

Выходной файл должен содержать N первых чисел последовательности Фибоначчи.

Ограничения

0 ≤ N ≤ 94

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

2

0 1

Задача C2. Подсчёт баллов за задачу ≡

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в a_i баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

Формат входного файла

В первой строке файла содержится единственное число N.

Во второй строке файла содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

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

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача C3. GCD ≡

Условие

Дано 3 числа: A, B, C. Необходимо посчитать наибольший общий делитель (НОД) каждой из пар A и B, A и C, B и C

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

Входные данные содержат 3 числа — A, B, C.

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

Выходные данные должны содержать 3 числа — НОД A и B, НОД A и C и НОД B и C

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

2 6 3

2 1 3

Задача C4. Марсианские суеверия ≡

Условие

Недавно стало известно, что все марсиане (как и некоторые люди) боятся чисел 4 и 13. Поэтому в домах на Марсе квартиры и этажи пронумерованы так, что 4-ых и 13-ых квартир и этажей нет. Квартиры и этажи нумеруются подряд начиная с единицы, но после трёх следует пять, а после двенадцати — четырнадцать.

Марсиане часто путаются в такой нумерации квартир и этажей. Например, они не могут определить номер этажа, на котором находится интересующая их квартира.

Требуется написать программу, которая по данному количеству этажей марсианского дома N и количеству квартир на этаже M определяет, есть ли в нём квартира с номером K и, если есть, выводит номер этажа, на котором она расположена.

Формат входного файла

Во входном файле содержатся числа N M K.

Формат выходного файла

В выходном файле должно содержаться единственное число — номер этажа, на котором находится квартира с номером K, либо  − 1 если такой квартиры в доме нет.

Ограничения

1 ≤ N, M, K ≤ 10⁹

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

7 4 14

3

4 5 21

5

4 5 27

-1

5 7 4

-1

Задача C5. Две пешки и слон ≡

Условие

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

Шахматная доска имеет размер 8 на 8. Слон бьет ближайшую фигуру на каждом из четырех диагональных направлений от себя.

Формат входного файла

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

Формат выходного файла

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача D2. Поворот отрезка ≡

Условие

Вершины отрезка AB имеют координаты (X_a; Y_a) и (X_b; Y_b).

Требуется найти координаты вершин отрезка A^* B^* (X^*_a; Y^*_a) и (X^*_b; Y^*_b), полученного путём поворота отрезка AB вокруг точки O (X_o; Y_o) на β градусов.

Формат входного файла

Входной файл содержит целые числа X_a, Y_a, X_b, Y_b, X_o, Y_o, β

Формат выходного файла

Выходной файл должен содержать четыре вещественных числа X^*_a, Y^*_a, X^*_b, Y^*_b с точностью 10^− 3.

Ограничения

0 ≤ |X_a|, |Y_a|, |X_b|, |Y_b|, |X_o|, |Y_o| ≤ 10⁵

0 ≤ β  ≤ 360

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

1 1  2 2  0 0  90

-1.000000000 1.000000000 -2.000000000 2.000000000

1 1  2 2
0 0
45

0.000000000 1.414213562 0.000000000 2.828427125

7 5
11 11
9 8
180

11.000000000 11.000000000 7.000000000 5.000000000

Задача D3. Количество каждого числа ≡

Условие

Вася записал в файл input.txt N чисел. Когда Петя открыл этот файл, он решил посчитать, сколько раз в файле записано каждое число.

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

Заметим, что это позволяет выполнить сортировку массива чисел по возрастанию при помощи простого подсчёта.

Формат входного файла

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

Формат выходного файла

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

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

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

4
1 2 1 0

0 1
1 2
2 1

7
9 1 3 2 3 -2 7

-2 1
1 1
2 1
3 2
7 1
9 1

Задача D4. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

Формат входного файла

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

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

5
1 2 3 4 5
3
1 3
2 5
3 5

6 14 12

Задача E1. Максимум в массиве ≡

Условие

Вводится массив, состоящий из целых чисел. Найти наибольшее среди них

Формат входного файла

Сначала задано число N — количество элементов в массиве (1 ≤ N ≤ 35). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел в диапазоне от  − 2³¹ до 2³¹ − 1.

Формат выходного файла

Необходимо вывести значение наибольшего элемента в массиве.

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

3
1 2 3

3

Задача E2. Ксюша и массив ≡

Условие

Ксюша — начинающий программист. Сегодня она знакомится с массивами. У нее есть массив a₁, a₂, …, a_n, состоящий из n целых положительных чисел. Преподаватель в университете задал ей задачу. Найти такое число в массиве, на которое делятся все элементы массива. Помогите ей, найдите это число!

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

В первой строке вводится целое число n (1 ≤ n ≤ 10⁵) — количество элементов в массиве. В следующей строке через пробел содержатся целые числа a₁, a₂, …, a_n(1 ≤ a_i ≤ 10⁹) — элементы массива.

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

Выведите единственное целое число — число из массива, на которое делятся все элементы массива. Если такого числа нет, выведите  − 1.

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

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

3
2 2 4

2

5
2 1 3 1 6

1

3
2 3 5

-1

Задача E3. Частотная матрица ≡

Условие

Вам дана матрица целых неотрицательных чисел A_ij. Требуется вычислить частотную матрицу B_ij, где B_ij — число вхождений числа j в строку с номером i матрицы A. Вычисление частот следует выполнить только для чисел от min A_ij до max A_ij.

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

Первая строка входного файла содержит целые числа N, M — размеры матрицы A.

Следующие N строк содержат M целых неотрицательных чисел каждая — числа матрицы A_ij.

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

Выходной файл должен содержать матрицу размера N × max A_ij — матрицу B.

Ограничения

1 ≤ N, M ≤ 10000

N ⋅ M ≤ 10⁶

0 ≤ A_ij ≤ 100

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

3 2
1 2
1 1
2 2

0 1 1
0 2 0
0 0 2

Задача E4. Dot первого и последнего столбцов матрицы ≡

Условие

Требуется написать программу, которая скалярно перемножает первый и последний столбец матрицы. Скалярным произведением двух векторов будет скалярная величина, равная сумме попарного произведения координат векторов (Например (1, 2, 3) ⋅ (3, 4, 5) = 1 * 3 + 2 * 4 + 3 * 5 = 26).

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

Первая строка содержит числа N и M — количество строк и столбцов матрицы. Следующие N строк содержат M чисел каждая — элементы матрицы.

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

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

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

2 2
1 3
4 5

23

Задача E5. Обход матрицы: спиральный обход ≡

Условие

• в левом верхнем углу находится число 1
• далее числа располагаются по спирали, закрученной вправо и внутрь

Формат входного файла

Формат выходного файла

Ограничения

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

2

1 2
4 3

3

1 2 3
8 9 4
7 6 5

Задача E6. Собственное значение матрицы ≡

Условие

Дана матрица 2 × 2, в которой одно из значений неизвестно. Оно обозначено буквой X (X всегда находится в одой и той же позиции). Также известно собственное значение матрицы λ.

Требуется определить значение X.

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

Первая строка входных данных содержит два вещественных числа a₁₁ и a₁₂. Во второй строке содержится вещественное число a₂₁ и символ X. Третья строка содержит одно вещественное число λ

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

Первая строка выходных данных должна содержать строку NO если такого X не существует, INF если значений X бесконечно много и YES если такое значение одно. В случае, если существует одно значение X, следует вывести число X с точностью не менее 4 знаков после запятой.

Ограничения

 − 10⁶ ≤ a₁₁, a₁₂, a₂₁, λ  ≤ 10⁶

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

1 2
2 X
5

YES
4.00000000000000000000

5 2
2 X
5

NO

5.0 0.0
2.0 X
5.0

INF

Problem E7. Guess the array ≡

Statement

Aleksey lost his favourite array a! He remembers that the array consisted of n non-negative integers, and its sum was equal to sum.

Recently Aleksey found his calculations on this array. His calculations consist of n numbers b_i such that

b_i = (a_i + a_i + 1)mod k for 1 ≤ i < n

b_n = (a_n + a₁)mod k (a_i — favourite array numbers)

Help Aleksey to find any correct favourite array a corresponding to the array b, or tell him that he has made a mistake, and there is no such array. Notice, that all elements of source array are non-negative integers that are not greater than 10⁴.

Input format

The first line contains three integers n, k, sum.

The next line contains n non-negative integers b_i.

Output format

If the answer exists, print "YES" in the first line and n space separated numbers of array a in the second line. If there are multiple answers, print any of them.

Print "NO" if there is no such array.

Constraints

2 ≤ n, k ≤ 10⁴

0 ≤ sum ≤ 10⁹

0 ≤ a_i ≤ 10⁴

0 ≤ b_i < k

Sample tests

6 4 21
3 1 3 1 3 3

YES
1 2 3 4 5 6

2 7 32
4 4

YES
11 21

6 4 21
1 3 2 1 3 2

NO

Problem E8. Implicit array ≡

Statement

Sorted array of integers is represented implicitly. Instead of each element, a set of that element and its neighbors on the right and on the left is known. First and last array elements have no more than one neighbor. Note that the set does not represent neither the order of elements nor duplicate values.

Your program must output explicit representation of the array (all elements in order).

Input file format

First line of input file contains integer N — number of elements in array.

Following N lines contain implicit representation of array elements: set size s_i and s_i different integers a_ij — a set of i-th array element and its neighbors.

Output file format

Output file must contain N integers — elements of original sorted array.

Constraints

1 ≤ N ≤ 10⁵

 − 10⁹ ≤ a_ij ≤ 10⁹

Sample tests

7
1 1
1 1
2 1 2
2 1 2
2 2 3
2 2 3
1 3

1 1 1 2 2 3 3

1
1 7

7

Problem E9. Ganking ≡

Statement

Popular on-line game "Attack Of The Moderns 3" is played by two teams of 5 players each. During the match, players run around the map and try to kill members of opposing team by attacking them with various weapons and magic spells. Killed players respawn after a certain period of time.

Players of the first team are numbered from 1 to 5, players of the second team are numbered from 6 to 10. All attacks are recorded by the game for statistics gathering. Each attack is described by values t, a, v, k, where t is a time in seconds since the game start, a — the number of the attacking player, v — the number of the player being attacked, k = 1 if this attack killed the victim and 0 otherwise.

Gank is an event when one or more players attack and kill a single opponent while his teammates are elsewhere and unable to help. Specifically: let G be a set of players who attacked the victim during the last T seconds of the game before the kill. A kill is counted as a gank, if in that period of time:

• the victim only attacked players from set G, and
• players from set G attacked and were attacked only by the victim.

Your program must, given the value of T and a sequence of N attack descriptions, count the number of ganks each player has participated in.

Input file format

Input file contains integers N T followed by N quartets of integers t_i a_i v_i k.

Output file format

Output file must contain 10 integers — the numbers of ganks for each player.

Constraints

1 ≤ N ≤ 10000, 1 ≤ t_i ≤ t_i + 1 ≤ 10⁵, 1 ≤ T ≤ 10⁵. Either 1 ≤ a_i ≤ 5 < v_i ≤ 10 or 1 ≤ v_i ≤ 5 < a_i ≤ 10. Time between sequential kills of the same victim is greater than T.

Sample tests

7 4
1 1 6 0
2 2 6 0
5 3 6 1
10 7 1 1
10 7 2 1
20 8 1 1
20 3 7 1

0 1 2 0 0 0 0 1 0 0 

Problem F1. Elite number ≡

Statement

Let's call an integer number elite if it is divisible by every digit of its decimal representation.

Given an integer x, your program must find the smallest elite number greater than or equal to x.

Input file format

Input file contains the integer x.

Output file format

Output file must contain a single integer — the smallest elite number.

Constraints

1 ≤ x ≤ 10¹⁰

Sample tests

10

11

7777777777

7777777777

579916

593595

Задача G1. Почтовый индекс ≡

Условие

У Тимофея скоро День рождения! В связи с этим эпохальным событием, он собирается сделать рассылку писем-приглашений. К сожалению, отправить почтовый конверт не так просто, как электронное письмо, необходимо знать точный домашний адрес, а самое главное — почтовый индекс адресата.

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

Линии, образующие стороны квадрата, Тимофей называет прямыми, а диагонали квадрата - наклонными. Например, в цифре 9 четыре прямых и одна наклонная линия.

Сегодня Тимофей должен написать письмо-приглашение своему другу, с которым он познакомился в международном лагере юных программистов, да вот беда - Тимофей совсем забыл его почтовый индекс. Все, что он помнит, так это количество прямых и наклонных линий в его индексе, и то, что он является наименьшим натуральным числом из всех подходящих. Помогите Тимофею! Учтите, что длина индекса в других странах может быть произвольной (а не 6, как в России), а также то, что никакой индекс не может начинаться с нуля.

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

В единственной строке через пробел записаны два неотрицательных целых числа a и b — количества прямых и наклонных линий в индексе.

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

Выведете одно натуральное число — наименьший подходящий индекс. Если ни одного подходящего индекса подобрать нельзя, выведите сообщение Wrong.

Ограничения

0 ≤ a ≤ 10³

0 ≤ b ≤ 10²

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

10 1

28

5 4

Wrong

23 5

100236

Задача G2. Код Хаффмана ≡

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

Формат входного файла

Формат выходного файла

Ограничения

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

6
45
13
12
16
9
5

0
101
100
111
1101
1100

Задача G3. Горячий кофе ≡

Условие

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

Формат входного файла

В первой строке входного файла содержится два целых числа — n и p. Во второй строке записаны n целых чисел a₁, a₂, …, a_n, задающих время прихода каждого программиста на работу (время считается от начала рабочего дня в тех же единицах, в которых необходимо выдать ответ).

Формат выходного файла

В выходной файл выведите единственное число — ответ к задаче.

Ограничения

2 ≤ n ≤ 10⁶;

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

3 2
0 30 10 

30

Задача G4. Восстановление сетки ≡

Условие

Турнир по олимпийской системе, состоящий из N раундов, проводятся между 2^N участниками по следующей схеме: сначала составляется последовательность из расставленных в произвольном порядке игроков. В первом раунде первый в последовательности участник соревнуется со вторым, третий с четвёртым, и т.д. Проигравшие выбывают из турнира, и на втором раунде победитель первой пары играет с победителем второй, победитель третьей с победителем четвёртой, и т.д. Наконец, после N-го раунда остаётся ровно один участник, который становится победителем турнира.

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

Рекомендуется рассмотреть частичные решения

N ≤ 10;

Формат входного файла

Входной файла содержит целое число N, за которым следуют 2^N − 1 пар чисел W_i L_i, означающих, что участник с номером W_i победил участника с номером L_i. Участники пронумерованы от 1 до 2^N.

Формат выходного файла

Выходной файл должен содержать 2^N целых чисел — номера участников, перечисленные в соответствии с упорядоченной первоначальной расстановкой.

Ограничения

1 ≤ N ≤ 20

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

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

7 8 6 5 3 4 1 2 

Задача G5. Миллион Z ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

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

3
A 1 50
X 90 1000
D 30 1000000

2

Задача G6. Автостоянка на улице Кантора ≡

Условие

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

Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.

Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).

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

Рекомендуется рассмотреть частичные решения

N = 1

C ≤ 10⁶

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ C_i ≤ 10⁹

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

1
1

1 0

2
20101204
226

6106 234
4 16

Задача G7. Дерево Штерна-Броко ≡

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида m / n называется деревом Штерна-Броко.

Начнем с дробей 0/1 и 1/0, а затем будем повторять следующую операцию: вставить дробь (m + m′) / (n + n′) между двумя соседними дробями m / n и m′ / n′.

Например первый шаг дает одну новую дробь между 0/1 и 1/0: 0/1, 1/1, 1/0. Следующий шаг добавляет две дроби, получая 0/1, 1/2, 1/1, 2/1, 1/0. Весь процесс можно представить в виде бесконечного бинарного дерева (см. рисунок).

Воспользуемся символами L и R для обозначения левой и правой ветвей при продвижении от корня вниз к определенной дроби. Тогда строка символов L и R однозначно определяет местоположения дроби в дереве. Например, строка LRRL соответствует дроби 5/7.

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать строку, являющаяся представлением дроби в дереве Штерна-Броко.

Ограничения

1 ≤ N, M ≤ 10⁵; N ≠ M

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

5 7

LRRL

Задача I1. Скобочная последовательность ≡

Условие

Скобочная последовательность - это последовательность символов скобок (любых видов). Скобочная последовательность называется правильной, если каждой открывающей скобке найдется соответствующая закрывающая того же типа и наоборот. При этом скобочные подпоследовательности правильной скобочной последовательности могут быть вложенны друг в друга, но не могут пересекаться. Будем называть глубиной скобочной последовательности в позиции i количество открывающих скобок левее позиции i + 1, которым еще не нашлись соответствующие закрывающие скобки.

Для заданной скобочной последовательности выведите ее максимальную глубину. В случае, если она не является правильной, выведите  − 1.

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

На вход подается одна строка - набор символов '(', ')', '[', ']', '', ''

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

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

Ограничения

Длина строки не превышает 10⁵

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

(())

2

([]{})

2

{[}]

-1

Задача I2. Очередь к врачу ≡

Условие

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

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

Первая строка входных данных содержит два целых числа N — количество посетителей за последний день и K — длительность приема одного пациента.

Вторая строка содержит N чисел, отсортированных по возрастанию: t_i  — время, когда i − ый посетитель пришел на прием к терапевту.

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

0 ≤ t_i ≤ 10⁹

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

5 5
0 5 5 6 20

2

5 2
1 4 6 8 20

0

6 5
0 5 10 15 19 25

1

Задача I3. Ближайшее число ≡

Условие

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

Формат входного файла

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

Формат выходного файла

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача I4. Антон и магазин радиодеталей ≡

Условие

Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа a_i (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.

Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.

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

Помогите Антону узнать, какое минимальное количество раз ему придётся складывать новую деталь в тележку.

Примечание

Рекомендуется рассмотреть частичные решения для N ≤ 1000, a_i ≤ 10⁵.

Формат входного файла

Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел a_i.

Формат выходного файла

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

Ограничения

1 ≤ N, K ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

3 3 
1 2 3

3

5 2
1 1 1 2 2

2

7 3
8 2 3 1 1 2 2

4

Задача J1. Гаджет в кредит ≡

Условие

Студент Вася решил приобрести себе новый гаджет. Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.

В магазине Васе объяснили правила предоставления кредита.

• Первоначально сумма долга равна стоимости гаджета C.
• По истечении максимум N лет вся сумма долга должна быть выплачена
• Вася должен определить ежемесячный платеж M — целое число рублей, которое он будет выплачивать каждый месяц. Исключение может составлять последний платёж — оставшаяся на последний месяц сумма долга может оказаться меньше M.
• Каждый месяц после Васиного платежа оставшаяся сумма долга увеличивается на P процентов и округляется вверх до целого числа.

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

Рекомендуется рассмотреть частичные решения

1. P = 0
2. C, P ≤ 10³

Формат входного файла

Входной файла содержит целые числа N P C.

Формат выходного файла

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

Ограничения

1 ≤ C ≤ 10⁹; 0 ≤ P ≤ 10⁹; 1 ≤ N ≤ 10⁴

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

1 0 1

1

1 124 12

8

1 1 12

2

Задача J2. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

Формат входного файла

Входной файл содержит три целых числа: W, H, N

Формат выходного файла

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Problem Z1. Fence relicts ≡

Statement

The Nearsea region has a large forest, where many relict trees grow. The local government decided to create a reservation park with the area between 0 and S square meters. The park must have a shape of rectangle with the sides parallel to coordinate axises.

Environment activists surveyed the forest and found out that it contained N relict trees located at coordinates (x_i, y_i), measured in meters.

Find such park location and size that the number of relict trees inside of it or on its boundary is maximum possible.

Input file format

Output file format

Constraints

1 ≤ N ≤ 500,  − 10⁴ ≤ x_i, y_i ≤ 10⁴, 1 ≤ S ≤ 10⁹

Sample tests

5 100
0 0  10 0  10 10  0 10  15 10

0 0 10 10

3 2
0 0  10 0  20 0

0 0 20 0