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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2 3
5
2
17 -18
-1

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

Автор:П. Месенёв   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2.0 3.0 0
5.0

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

Автор:П. Месенёв, А. Маметьев, Yandex cup   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 5 * 1011

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

Стандартный вход Стандартный выход
1
3
1
2
5
3

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

Автор:mesenev   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ n ≤ 16777215

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

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

Стандартный вход Стандартный выход
1
6579300 g
25600

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

Автор:Р. Болотаев   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

0 ≤ n ≤ 18446744073709551615

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

Стандартный вход Стандартный выход
1
0
NO
2
47806
YES

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:2 Мб

Условие

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2.0
1
2
0.5
-1

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

Автор:Властелин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 2 3 4
4

Задача B4. FizzBuzz

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

Стандартный вход Стандартный выход
1
23
2
25
Buzz
3
30
FizzBuzz

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

Ограничения

1 < n < 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 5
3

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

Автор:Властелин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

0 ≤ a, b, c ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 5 2
-0.6667 -1.0000
2
0 7.245 -5.222
0.7208 0.7208

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000

 − 109 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 2 3 4
4 3 2 1
2
6
9 1 3 -2 3 5
5 3 -2 3 1 9

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

Автор:Властелин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 94

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
0 1

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 5 10 
+-++-
9
2
6
1 1 3 5 10 25
+-+--+
29

Задача C3. GCD

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2 6 3
2 1 3

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M, K ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 4 14
3
2
4 5 21
5
3
4 5 27
-1
4
5 7 4
-1

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

Входной файл содержит числа x1 y1 x2 y2 — координаты первой и второй пешек.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 6 7 5
0
2
3 4 5 6
4 5
3
4 5 5 6
0

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

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

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

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

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

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

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ ai ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 2 1 0
0 1
1 2
2 1
2
7
9 1 3 2 3 -2 7
-2 1
1 1
2 1
3 2
7 1
9 1

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

Автор:Г. Гренкин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дан массив целых чисел a1, a2, ..., aN и дано M команд типа "найти сумму чисел ai для i от l до r".

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ ai ≤ 1000

1 ≤ lj ≤ rj ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 4 5
3
1 3
2 5
3 5
6 14 12

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
3

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

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:64 Мб

Условие

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

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

В первой строке вводится целое число n (1 ≤ n ≤ 105) — количество элементов в массиве. В следующей строке через пробел содержатся целые числа a1, a2, …, an(1 ≤ ai ≤ 109) — элементы массива.

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

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

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

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

Стандартный вход Стандартный выход
1
3
2 2 4
2
2
5
2 1 3 1 6
1
3
3
2 3 5
-1

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

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10000

N ⋅ M ≤ 106

0 ≤ Aij ≤ 100

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

Стандартный вход Стандартный выход
1
3 2
1 2
1 1
2 2
0 1 1
0 2 0
0 0 2

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2 2
1 3
4 5
23

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

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

По данному числу N требуется заполнить квадратную матрицу размером NxN целыми числами от 1 до N2; следующим образом:

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

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

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

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

Ограничения

1 <= N <= 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
4 3
2
3
1 2 3
8 9 4
7 6 5

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

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

Ограничения

 − 106 ≤ a11, a12, a21, λ ≤ 106

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

Стандартный вход Стандартный выход
1
1 2
2 X
5
YES
4.00000000000000000000
2
5 2
2 X
5
NO
3
5.0 0.0
2.0 X
5.0
INF

Problem E7. Guess the array

Author:N. Grebenyuk   Time limit:2 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

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 bi such that

bi = (ai + ai + 1)mod k for 1 ≤ i < n

bn = (an + a1)mod k (ai — 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 104.

Input format

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

The next line contains n non-negative integers bi.

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 ≤ 104

0 ≤ sum ≤ 109

0 ≤ ai ≤ 104

0 ≤ bi < k

Sample tests

No. Standard input Standard output
1
6 4 21
3 1 3 1 3 3
YES
1 2 3 4 5 6
2
2 7 32
4 4
YES
11 21
3
6 4 21
1 3 2 1 3 2
NO

Problem E8. Implicit array

Author:М. Спорышев   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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 si and si different integers aij — 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 ≤ 105

 − 109 ≤ aij ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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
2
1
1 7
7

Problem E9. Ganking

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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:

All the players from the set G who attacked the victim of the gank are considered the participants of this gank.

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 ti ai vi k.

Output file format

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

Constraints

1 ≤ N ≤ 10000, 1 ≤ ti ≤ ti + 1 ≤ 105, 1 ≤ T ≤ 105. Either 1 ≤ ai ≤ 5 < vi ≤ 10 or 1 ≤ vi ≤ 5 < ai ≤ 10. Time between sequential kills of the same victim is greater than T.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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 ≤ 1010

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
10
11
2
7777777777
7777777777
3
579916
593595

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

Автор:Антон Карабанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

Ограничения

0 ≤ a ≤ 103

0 ≤ b ≤ 102

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

Стандартный вход Стандартный выход
1
10 1
28
2
5 4
Wrong
3
23 5
100236

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

Автор:stdalg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Выходной файл должен содержать N строк вида hi — коды Хаффмана для символов в порядке, соответствующем входному файлу. Каждый код должен представлять собой строку из цифр 0 и 1. Если существует несколько решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 100, 0 ≤ fi ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
45
13
12
16
9
5
0
101
100
111
1101
1100

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

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

Зная момент времени, в который каждый программист приходит на работу, помогите выбрать шефу наибольший целочисленный параметр t, который не приведёт к очереди длиннее p.

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

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

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

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

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

Ограничения

2 ≤ n ≤ 106;

1 ≤ p < n;

0 ≤ ai ≤ 109;

Все ai различны.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
0 30 10 
30

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

Автор:И. Лудов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

N ≤ 10;

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

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

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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

Входной файл:input.txt   Ограничение времени:5 сек
Выходной файл:output.txt   Ограничение памяти:8 Мб

Условие

Дана строка, состоящая из одного миллиона букв "Z". Определим операцию замены, которая характеризуется тремя параметрами (α, i, j) и состоит в замене на букву α букв строки начиная с позиции i до позиции j. Требуется определить, сколько различных букв будет в строке после выполнения заданной последовательности операций замены.

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

В первой строке входного файла содержится число замен N. В следующих N строках содержатся тройки α i j, где α — заглавная латинская буква, i и j — целые числа.

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

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

Ограничения

0 ≤ N ≤ 1000, 1 ≤ i ≤ j ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
A 1 50
X 90 1000
D 30 1000000
2

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

Автор:В. Степанец, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

013610
24711
5812
913
14

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

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

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

N = 1

C ≤ 106

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

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

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

Выходной файл должен содержать N пар чисел xi yi — координаты мест, соответствующие номерам во входном файле.

Ограничения

1 ≤ N ≤ 105

0 ≤ Ci ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
1 0
2
2
20101204
226
6106 234
4 16

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

Автор:Штерн, Броко, Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида 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 ≤ 105; N ≠ M

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7
LRRL

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

Автор:Известная   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

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

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

Стандартный вход Стандартный выход
1
(())
2
2
([]{})
2
3
{[}]
-1

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

Автор:Михалев Ю.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ K ≤ 109

0 ≤ ti ≤ 109

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

Стандартный вход Стандартный выход
1
5 5
0 5 5 6 20
2
2
5 2
1 4 6 8 20
0
3
6 5
0 5 10 15 19 25
1

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

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

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

Автор:М. Спорышев, И. Блинов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Примечание

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

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

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

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

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

Ограничения

1 ≤ N, K ≤ 105

0 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 
1 2 3
3
2
5 2
1 1 1 2 2
2
3
7 3
8 2 3 1 1 2 2
4

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

Автор:М. Спорышев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

  1. P = 0
  2. C, P ≤ 103

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

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

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

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

Ограничения

1 ≤ C ≤ 109; 0 ≤ P ≤ 109; 1 ≤ N ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0 1
1
2
1 124 12
8
3
1 1 12
2

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:diploma.in   Ограничение памяти:64 Мб
Выходной файл:diploma.out  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ W, H, N ≤ 109

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

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

Problem Z1. Fence relicts

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

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 (xi, yi), 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

Input file contains integers N S followed by N pairs of integers xi yi.

Output file format

Output file must contain integers xa ya xb yb — coordinates of the two opposite corners of the park. If there is more than one optimal solution, output any of them.

Constraints

1 ≤ N ≤ 500,  − 104 ≤ xi, yi ≤ 104, 1 ≤ S ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 100
0 0  10 0  10 10  0 10  15 10
0 0 10 10
2
3 2
0 0  10 0  20 0
0 0 20 0

1.822s 0.009s 105