Задача 1A. Сумма квадратов

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

Условие

Дано неотрицательное целое число N. Требуется определить, существуют ли такие неотрицательные целые числа x и y, что x2 + y2 = N.

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

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

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

Выходной файл должен содержать искомую пару целых чисел x y, или  − 1. если такой пары не существует. При наличии нескольких решений вывести любое из них.

Ограничения

0 ≤ N ≤ 1000

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

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

Задача 1B. Имя для аллигатора

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

Условие

Вася купил аллигатора и строку s, теперь он хочет выбрать для аллигатора имя, которое будет подстрокой строки s. Имя аллигатора не должно быть длиннее 100 символов или короче 5 символов.

Вася считает слогом пару букв, в которой первая буква согласная, а вторая гласная. Красотой имени называется количество слогов в имени.

Помогите Васе посчитать максимальную красоту имени для аллигатора.

Гласные буквы: A, E, I, O, U, Y

Согласные буквы: B, C, D, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, X, Z

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

Первая строка входного файла содержит строку s.

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

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

Ограничения

Длина строки s не превосходит 5 ⋅ 104 и не меньше чем 5, строка состоит из заглавных букв.

Описание подзадач и системы оценивания

Решения работающие для длины s не превосходящей 103 оцениваются из 40 баллов.

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

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

Задача 1C. Короткий текст и немного слов

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

Условие

Имеется текст и N слов. Длина текста L символов, длина каждого слова — от 1 до 255 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными.

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

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

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

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

Ограничения

1 ≤ L ≤ 255, 1 ≤ N ≤ 1000.

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

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

Задача 1D. Самая высокая стопка монет на всём Дальнем Востоке

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

Условие

В Берляндии в обиходе монеты достоинством 1, 2, 3, 4, 5 и 6 бурлей, толщина всех монет одинаковая. У Васи есть неограниченное количество монет каждого достоинства. Вася и Петя играют в следующую игру: Петя загадывает сумму S, которую необходимо набрать, и сообщает Васе число N — количество монет, которые Вася может использовать. После этого Вася должен подобрать такие N монет, чтобы их сумма равнялась ровно S бурлям. Далее все N монет раскладываются в 6 стопок по номиналам.

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Решение будет полностью проверяться сразу после отправки, и участникам будут видны набранные за данную задачу баллы.

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

Первая строка входного файла содержит целое число M — количество пар "сумма-количество". Последующие M строк содержат по 2 целых числа — S, N — сумма и заданное количество монет.

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

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

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

Стандартный вход Стандартный выход
1
1
30 6
0 0 0 0 6 0 

Задача 1E. Убрать соседа

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

Условие

Дан массив чисел. Необходимо удалить элементы, за которыми в этом массиве следует ноль.

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

Входные данные содержат ряд чисел, разделенных пробелом.

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

Выходные данные должны содержать преобразованный массив.

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

Стандартный вход Стандартный выход
1
1 2 0 3 4 0 5 10
1 0 3 0 5 10
2
11 0 0 12
0 12

Задача 2A. Бутылка на всех

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

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 105

0 ≤ ai ≤ 109

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

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

Задача 2B. Жадная последовательность

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

Условие

Дана последовательность из N целых чисел ai. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

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

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

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

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

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

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 105

 − 104 ≤ ai ≤ 104

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
nm
1202 ≤ n ≤ 5m < nполная
2202 ≤ n ≤ 1000m < n1полная
3602 ≤ n ≤ 105m < n1,2полная

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

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

Задача 2C. Найм рабочих

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

Условие

Прораб распланировал работы на n дней вперёд, в день i выполняется только один тип работ ai и при этом требуется ci работников. В компании нет постоянных сотрудников, каждый день нанимаются новые работники для выполнения работ.

Так же у прораба имеется список из m работников. j-й работник имеет компетенции на kj различных работ и работник просит pj денег за один день работы (в независимости от типа выполняемых работ).

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

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

Первая строка входного файла содержит два целых числа n и m. Далее следует n строк содержащих по два целых числа ai и ci. Следующие m строк содержат два целых числа kj и pj, количество компетенций и зарплата за день сотрудника с номером j, далее в этой строке идут kj чисел, номера работ которые может выполнять сотрудник с номером j.

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

Выходной файл должен содержать n целых чисел, i-e число минимальное количество денег которое нужно потратить в день i.

Ограничения

0 ≤ n, m, ki ≤ 105; 1 ≤ ai ≤ 109; 1 ≤ pi ≤ 100

Сумма по всем ki не превосходит 2 ⋅ 105.

Описание подзадач и системы оценивания

Решения работающие для 0 ≤ n, m, ki ≤ 103; 1 ≤ ai, pi ≤ 103, сумма по всем ki не превосходит 2 ⋅ 103 оцениваются из 40 баллов.

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

Стандартный вход Стандартный выход
1
5 3
1 1
2 1
3 1
1 3
1 2
3 100 1 2 3
3 10 1 2 3
1 1 1
1
10
10
111
11
2
1 4
229 4
2 23 1 229
2 22 4 229
2 11 229 15
3 21 65 43 229
77

Задача 2D. Cut the band

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

Условие

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

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

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

Напишите программу, которая определит минимальное число разрезов, которое придётся сделать Васе чтобы подарить все кусочки ленточки.

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

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

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

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

Четвертая строка входного файла содержит M целых чисел bi — нелюбимое число i-го друга. Все bi различны.

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

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

Ограничения

1 ≤ N ≤ 105

2 ≤ M ≤ 105

1 ≤ ai, bi ≤ 109

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

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

Задача 2E. Золотая середина

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

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер k / 2, считая с единицы).

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

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

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

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

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

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

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

Задача 3A. Наибольший общий делитель

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

Условие

Дается N чисел. Требуется найти их наибольший общий делитель.

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

Первая строка содержит одно целое число - N

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

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

Выходные данные должны содержать единственное число - наибольший общий делитель чисел.

Ограничения

1 ≤ N ≤ 105

1 ≤ ai < 264

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

Стандартный вход Стандартный выход
1
2
12 16
4
2
2
25 9
1
3
3
12 27 15
3

Задача 3B. Наименьший общий делитель

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

Условие

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

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

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

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

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

Ограничения

1 ≤ A, B ≤ 231 − 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 20
2
2
13 17
1

Задача 3C. Простые числа

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

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 1000

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

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

Задача 3D. Небоскреб

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

Условие

Артем и Женя обожают строить здания из кубиков. Они уже строили из них гаражи, домики, и даже средневековые замки... Сегодня ребята решили возвести небоскреб. У Артема есть n синих кубиков, а у Евгения m красных. По мысли ребят, построенный небоскреб должен представлять собой два прямоугольных параллелепипеда с квадратными основаниями разного размера, установленные один на другой. Мальчики хотят, чтобы каждый из них построил свою часть многоэтажного строения исключительно из всех своих кубиков, а потом установить один параллелепипед на другой.

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

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

Первая строка входного файла содержит три натуральных числа, записанных через пробел: n, m и k.

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

Выведите одно неотрицательное целое число - наибольшую высоту построенного небоскреба.

Ограничения

1 ≤ n, m, k ≤ 109

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

В первом примере у Артема 729 кубиков, а у Жени 1024. Наибольшая высота небоскреба, который может быть построен дома, не может превышать 15. Ребята действуют так: сначала Евгений строит из своих кубиков основание небоскреба в виде прямоугольного параллелепипеда: 16 × 16 × 4 (обратите внимание - основание параллелепипеда обязательно должно быть квадратным). Потом Артем устанавливает сверху на постройку Жени свой прямоугольный параллелепипед: 9 × 9 × 9, и высота небоскреба становится равна 13. Большей высоты с учетом всех ограничений достичь нельзя.

Во втором примере у ребят не получится составить небоскреб. Артем может построить свою часть в виде единственно возможного прямоугольного параллелепипеда: 1 × 1 × 17, Женя (аналогично): 1 × 1 × 19. Но, во-первых, обе построенные ими части будут иметь равное основание, а во вторых, общая высота небоскреба 36 превышает высоту помещения.

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

Стандартный вход Стандартный выход
1
729 1024 15
13
2
17 19 30
0

Задача 3E. Square coins

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

Условие

"Сенсационная находка!", "Археологи обнаружили древнюю цивилизацию!", "Ученые поражены развитием древних технологий!" — такими заголовками пестрели новости. Обнаруженные под толщей песка пустыни Сахары артефакты действительно поражали: совершенные приборы и механизмы, манускрипты и пергаменты с непонятными записями, предметы искусства и быта - всё указывало на существовавшую когда-то в этом регионе развитую цивилизацию. Ученые нацелились на долгую и кропотливую работу.

Нумизматов же, конечно заинтересовала денежная система Древнесахарцев (так окрестили обнаруженную цивилизацию). Были найдены золотые монеты разного размера, все исключительно квадратной формы и с квадратным отверстием посередине. Что интересно - все размеры (и сторон монет, и сторон отверстий) были нечетными числами. Было высказано предположение, что стоимость монеты соответствовала её площади: так на монете размером 5 с отверстием 1 было отчеканено 24 точки, на монете размером 5 с отверстием 3 нашлось 16 точек, на монете размером 3 с отверстием 1 отчётливо видно 8 точек. Всё указывало на то, что стоимость монеты равна разности квадратов стороны монеты и стороны отверстия: 52 − 12 = 24, 52 − 32 = 16, 32 − 12 = 8.

По данной стоимости монеты определите все её возможные размеры.

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

Входные данные содержат целое число n — стоимость монеты. Гарантируется, что n кратно восьми.

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

В первой строке выведите целое число k — количество различных возможных размеров монет. В следующих k строках выведите по два числа: размер стороны монеты и размер отверстия. Записи упорядочите по возрастанию сторон монет.

Ограничения

8 ≤ n ≤ 1012

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

В примере дана стоимость монеты 72. Ей могут соответствовать три подходящих размера: 92 − 32 = 81 − 9 = 72, 112 − 72 = 121 − 49 = 72 и 192 − 172 = 361 − 289 = 72.

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

Стандартный вход Стандартный выход
1
72
3
9 3
11 7
19 17

Задача 4A. Факториал по модулю

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

Условие

Задано целое неотрицательное число n. Выведите n! по модулю 109 + 7.

Факториал числа n считается следующим образом:

n! = 1 ⋅ 2 ⋅ … ⋅ (n − 1) ⋅ n.

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

В первой и единственной строке входных данных задано целое число n (0 ≤ n ≤ 106).

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

Выведите единственное целое число: факториал числа n по модулю 109 + 7.

Ограничения

0 ≤ n ≤ 106

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

Стандартный вход Стандартный выход
1
5
120
2
1000000
641102369
3
0
1

Задача 4B. Возведение в степень

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

Условие

Вам необходимо по заданным двум неотрицательным целым числам a и b эффективно отвечать на вопрос: чему равен остаток от деления ab на 109 + 7?

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

Первая строка входных данных содержит единственное целое число n: количество запросов.

В каждой из следующих n строк содержатся два целых числа a и b.

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

Для каждого запроса выведите значение ab по модулю 109 + 7.

Ограничения

1 ≤ n ≤ 2 ⋅ 105

0 ≤ a, b ≤ 109

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

Стандартный вход Стандартный выход
1
3
3 4
2 8
123 123
81
256
921450052

Задача 4C. Возведение в (возведение в степень)

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

Условие

Вам необходимо по заданным трем неотрицательным целым числам a, b и c эффективно отвечать на вопрос: чему равен остаток от деления abc на 109 + 7?

Обратите внимание, что степени считаются справа налево, то есть abc = a(bc).

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

Первая строка входных данных содержит единственное целое число n: количество запросов.

В каждой из следующих n строк содержатся три целых числа a, b, c.

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

Для каждого запроса выведите значение abc по модулю 109 + 7.

Ограничения

1 ≤ n ≤ 105

0 ≤ a, b, c ≤ 109

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

Стандартный вход Стандартный выход
1
3
3 7 1
15 2 2
3 4 5
2187
50625
763327764

Задача 4D. abc-строка

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

Условие

Саша очень хочет построить строку s по следующим правилам:

1. Строка s состоит только из символов "a", "b" и "c";

2. В s содержится ровно na символов "a";

3. В s содержится ровно nb символов "b";

4. В s содержится ровно nc символов "c".

Перед тем, как построить строку, Саша заинтересовался тем, сколько различных строк он сможет построить. Будем считать, что он не ограничен во временных ресурсах. Саша не нашел ответа на этот вопрос, поэтому попросил вас посчитать это за него.

Так как ответ может быть очень большим, выведите его по модулю 109 + 7.

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

В первой и единственной строке входных данных содержится три целых числа na, nb и nc: количество каждого из символов соответственно. Гарантируется, что na + nb + nc ≥ 1.

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

Выведите ответ на задачу: количество всевозможных различных строк по модулю 109 + 7.

Ограничения

0 ≤ na, nb, nc ≤ 105

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

Стандартный вход Стандартный выход
1
1 1 1
6
2
2 2 5
756
3
100000 100000 100000
141974424

Задача 4E. Смишенное произведение

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

Условие

Миша очень любит изобретать новые операции. Недавно он изобрёл новую операцию, которую он в честь себя назвал смишенным произведением.

Смишенное произведение набора различных натуральных чисел a1, a2, …, an устроено следующим образом. Рассмотрим все возможные упорядоченные пары (ai, aj) различных чисел этого набора. Для каждой пары запишем эти числа подряд без пробела, получив новое число bij. Смишенным произведением чисел из исходного набора Миша называет сумму всех значений bij.

Помогите Мише посчитать смишенное произведение заданного набора чисел. Миша хочет вычислить его по модулю 109 + 7.

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

Первая строка содержит одно натуральное число n — количество чисел в наборе.

Вторая строка содержит n различных натуральных чисел a1, a2, …, an — числа набора.

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

Выведите одно число — остаток от деления смишенного произведения заданных чисел на число 109 + 7.

Ограничения

2 ≤ n ≤ 105

1 ≤ ai ≤ 108

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

Стандартный вход Стандартный выход
1
3
1 3 10
668

Задача 5A. Призы

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

Условие

Петр участвует в конкурсе, в котором разыгрывается N призов. Призы пронумерованы от 1 до N.

По итогам конкурса участник может набрать от 2 до N баллов. Если участник наберет K баллов, то он получит один из призов с номером от 1 до K.

Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов с номером от 1 до K. Затем участник может выбрать любой приз из оставшихся K − 1.

Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом ai.

Требуется написать программу, которая по заданным ценностям призов определяет для каждого K от 2 до N, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе K баллов.

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

Первая строка входного файла содержит число N. Вторая строка этого файла содержит N целых чисел: a1, a2, …, aN.

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

Выходной файл должен содержать одну строку, содержащую N − 1 целых чисел: для каждого K от 2 до N должна быть выведена ценность приза, который достанется Петру, если он наберет K баллов.

Ограничения

2 ≤ N ≤ 100000; 1 ≤ ai ≤ 109

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 1 (24 балла)

N ≤ 100

Подзадача 2 (24 балла)

N ≤ 5000

Подзадача 3 (52 балла)

N ≤ 100 000

Получение информации о результатах окончательной проверки

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

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

Входной файл (prizes.in) Выходной файл (prizes.out)
1
5
1 3 4 2 5
1 3 3 4 

Задача 5B. Лара Крофт и подвесной мост

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

Условие

Расхитительница гробниц Лара Крофт стоит на левом краю ущелья. Она хочет перебраться на правую сторону чтобы исследовать древний храм. Для этого ей нужно без остановок пробежать вперёд по подвесному мосту длиной N досок.

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

Оракул подсказал Ларе N чисел xi — номера секунд, в который обвалится i-ая доска подвесного моста. В нулевую секунду Лара стоит на левом краю ущелья.

Необходимо определить, сможет ли Лара перебраться на правую сторону ущелья и если да, то за сколько секунд.

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

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

Вторая строка содержит N целых чисел xi.

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

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

Если Лара не сможет добраться до другой стороны ущелья, выведите  − 1.

Ограничения

0 ≤ K ≤ 100

1 ≤ N ≤ 105

0 ≤ xi ≤ 2 ⋅ 105

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

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

Задача 5C. Треугольные и квадратные числа

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

Условие

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

Напомним, что число называется треугольным, если количество объектов, которое оно выражает, можно расставить в виде правильного треугольника. Аналогично, если это количество можно расставить в виде квадрата, то число называется квадратным.

На рисунке вы видите начало ряда треугольных чисел (1, 3, 6, 10, ...) и ряда квадратных чисел (1, 4, 9, 16, ...).

Тимофею нравится находить закономерности. Он смог доказать, что любое квадратное число (если оно больше 1) представимо в виде суммы всего двух треугольных чисел! Для поиска более сложных закономерностей ему нужно знать количество различных способов это сделать.

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

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

В единственной строке входного файла записано одно натуральное квадратное число n.

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

Выведите одно натуральное число - ответ на задачу.

Ограничения

4 ≤ n ≤ 1010

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

Комментарий к первому примеру: существует единственный способ представить 4 в виде суммы двух треугольных чисел: 4 = 3 + 1.

Комментарий ко второму примеру: существует два способа представить 16 в виде суммы двух треугольных чисел: 16 = 10 + 6 = 15 + 1.

Комментарий к третьему примеру: существует четыре способа представить 10000 в виде суммы двух треугольных чисел: 10000 = 5050 + 4950 = 5995 + 4005 = 8515 + 1485 = 9180 + 820.

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

Стандартный вход Стандартный выход
1
4
1
2
16
2
3
10000
4

Задача 5D. Caterpillar

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

Условие

Гусеница длины L ползёт по пересечённой местности. Пересечённую местность можно представить в виде одномерного массива из N клеток с разными высотами. Клетка ai называется спуском, если ai > ai + 1. Клетка ai называется подъёмом, если ai < ai + 1. Изначально гусеница занимает первые L клеток.

Чтобы продвинуться на одну клетку вперёд, гусеница тратит 1 секунду времени. Однако если среди занимаемых ей клеток спусков больше, чем подъёмов, и голова гусеницы находится на спуске, то она моментально продвигается вправо на одну клетку.

Определите, через сколько секунда голова гусеница достигнет последней клетки.

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

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

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

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

Ограничения

1 ≤ ai, N, L ≤ 106, L ≤ N, ai ≠ ai + 1

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

Стандартный вход Стандартный выход
1
1 4
4 3 2 3
1
2
3 10
10 9 8 7 8 9 10 9 8 7
4

Задача 5E. Подстрока с уникальными символами по краям

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

Условие

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

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

Входные данные содержат одну строку s.

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

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

Ограничения

2 ≤ |s| ≤ 106

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

В первом примере ответом могут быть подстроки abc и bcb. Во втором — bacab.

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

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

Задача 6A. Скучные дни

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

Условие

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

Чтобы не дать Васе умереть от скуки, вы должны срочно научиться отвечать на следующий вопрос: является ли промежуток с l по r день включительно скучным?

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

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

Вторая строка содержит N чисел:  − 1, если i-ый день был скучным, и 1 иначе.

Следующие M строк содержат запросы вида: li ri

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

Выходные данные должны содержать M строк - ответы на запросы

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

Ограничения

1 ≤ N ≤ 5 ⋅ 104

1 ≤ M ≤ 5 ⋅ 104

1 ≤ li ≤ ri ≤ N

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

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

Задача 6B. Призы

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

Условие

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

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

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

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

В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

Система оценивания и описание подзадач

В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (30 баллов)

3 ≤ n ≤ 50, 1 ≤ ai ≤ 105.

Подзадача 2 (30 баллов)

3 ≤ n ≤ 5000, 1 ≤ ai ≤ 105.

Подзадача 3 (40 баллов)

3 ≤ n ≤ 100 000, 1 ≤ ai ≤ 109.

Получение информации о результатах окончательной проверки

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

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

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

Вторая строка содержит n целых положительных чисел: a1, a2, …, an. Для каждого приза указана его ценность для Боба.

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

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

Ограничения

3≤ n ≤ 100 000, 1 ≤ k ≤ n / 3, 1≤ ai ≤ 109.

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

Входной файл (prizes.in) Выходной файл (prizes.out)
1
10 2
1 2 4 5 2 4 2 2 1 6
7

Задача 6C. Сумма

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

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

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

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

Изначально в массиве живут нули.

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

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

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

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

Задача 6D. Range Variation Query

Входной файл:rvq.in   Ограничение времени:2 сек
Выходной файл:rvq.out   Ограничение памяти:256 Мб

Условие

В начальный момент времени последовательность an задана следующей формулой: an = n2 mod 12345 + n3 mod 23456.

Требуется много раз отвечать на запросы следующего вида:

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

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ k ≤ 100 000).

Следующие k строк содержат запросы, по одному на строке. Запрос номер i описывается двумя целыми числами xi, yi.

Если xi > 0, то требуется найти разность между максимальным и минимальным значениями среди элементов axi, …, ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000.

Если xi < 0, то требуется присвоить элементу a|xi| значение yi.

В этом случае  − 100 000 ≤ xi ≤  − 1 и |yi| ≤ 100 000.

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

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

Ограничения

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

Входной файл (rvq.in) Выходной файл (rvq.out)
1
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
34
68
250
234
1

Задача 6E. Количество инверсий последовательнсти

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

Условие

Пара элементов (Ai, Aj) последовательности AN называется инверсией, если Ai > Aj и i < j.

Напишите программу, которая по заданной последовательности AN посчитает количество инверсий.

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

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

Последующие N целых чисел задают саму последовательность

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

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

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

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

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

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени: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

Задача 7B. В каждом рисунке - солнце

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

Условие

В столице Дальнего Востока проходит конкурс детских рисунков. Для оформления выставки работ финалистов организаторы планируют задействовать квадратный стенд. На одной стороне стенда будут размещены n вертикально ориентированных изображений одинакового размера w1 × h1. На второй стороне стенда будут размещены m горизонтально ориентированных изображений одинакового размера w2 × h2. При этом, согласно стандартам, расстояние между двумя рисунками, а также между рисунком и краем стенда должно быть не меньше 1, а стороны рисунков должны быть параллельны сторонам стенда.

Помогите организаторам рассчитать наименьшую сторону стенда, на котором возможно разместить все работы конкурсантов.

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

Единственная строка входного файла содержит шесть целых неотрицательных чисел, записанных через пробел: n, w1, h1, m, w2, h2. Гарантируется, что n и m не равны нулю одновременно.

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

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

Ограничения

0 ≤ n, m ≤ 109

1 ≤ w1, h1, w2, h2 ≤ 109

w1 ≤ h1

h2 ≤ w2

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при m = 0, получат не менее 20 баллов.

Решения, верно работающие при w1 = h2, h1 = w2, получат не менее 20 баллов.

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

В примере нужно на одной стороне стенда разместить пять вертикально ориентированных рисунков размером 2 × 3 и четыре горизонтально ориентированных размером 5 × 1 на противоположной. Минимальный подходящий размер стенда 10, один из вариантов размещения изображений - на рисунке.

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

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

Задача 7C. New function

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

Условие

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

Функция Тимофея определена на множестве натуральных чисел следующим образом: f(x) = x + ⌊ x10⌋  + ⌊ x100⌋  + ⌊ x1000⌋  + …, где ⌊ x10n означает округление результата деления вниз до целой части. Например, f(404) = 404 + ⌊ 40410⌋  + ⌊ 404100⌋  = 404 + 40 + 4 = 448.

Пока Тимофей оформляет статью в математический журнал, найдите такое число x, что f(x) = n.

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

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

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

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

Ограничения

1 ≤ n ≤ 1018

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

Стандартный вход Стандартный выход
1
448
404

Задача 7D. Мужик и два генерала

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

Условие

По сюжету сатирической сказки Михаила Салтыкова-Щедрина «Повесть о том, как один мужик двух генералов прокормил», два отставных генерала, выйдя на пенсию, неизвестным образом попадают на необитаемый остров. Они хотят выбраться с острова, однако не могут, поскольку даже не разбираются в сторонах света. Вскоре они решают найти мужика (то есть крестьянина), который сможет их вернуть домой. Генералы находят на острове мужика. Мужик строит для них лодку и переправляет через моря в Петербург. По прибытии в Петербург они наедаются, напиваются и едут в казначейство за деньгами. В благодарность за спасение с острова они посылают мужику рюмку водки и пятак серебра, восклицая: «Веселись, мужичина!».

Но у нас не сказка, а задача, да и генералы с тех пор слегка изменились, поэтому они будут помогать мужику строить лодку. Для её изготовления нужно n досок, каждый человек за один день способен сделать одну доску. Мужик, как архетип неутомимого народа, способен работать каждый день, а вот генералам нужен отдых, выходные и отпуск на море (хорошо, что место действия соответствует). Поэтому первый генерал работает a дней подряд, а потом b дней подряд отдыхает. Второй генерал работает c дней подряд, а потом d дней подряд отдыхает. Как скоро будет построена лодка?

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

Единственная строка входного файла содержит пять натуральных чисел, записанных через пробел: n - требуемое количество досок, a, b, c и d - расписание работы генералов.

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

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

Ограничения

1 ≤ n ≤ 1018.

1 ≤ a, b, c, d ≤ 1015.

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ n ≤ 106, получат не менее 40 баллов.

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

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

В первый день мужик и оба генерала делают по одной доске каждый.

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

В третий день работает только мужик, оба генерала отдыхают. Всего готово 6 досок.

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

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

В шестой день мужик и второй генерал делают по одной доске каждый, первый генерал отдыхает. Всего готово 11 досок - лодка построена. Работа завершена за 6 дней.

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

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

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

Задача 7E. Паркет

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

Условие

Андрей укладывает дома пол. У него длинный коридор длиной L.

У Андрея есть бесконечное количество досок, длины которых равны d. Необходимо полностью уложить пол досками. Доски можно пилить, но при этом в укладке нельзя использовать части досок короче c.

Сколько досок Андрею необходимо разрезать, чтобы уложить пол?

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

Входные данные содержат три целых числа: L, d, c.

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

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

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

Ограничения

1 ≤ L, d ≤ 109

0 ≤ c ≤ 109

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

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

Задача 8A. Рейд на босса

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

Условие

Вася играет в новую MMORPG и собирается пойти в рейд на босса. Однако, он столкнулся с двумя проблемами:

1. Он не знает на какого босса пойти

2. У него нет нужной экипировки для похода в рейд

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

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

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

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

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

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

Третья строка содержит M чисел: bi  — минимальный уровень вещей, необходимый для похода в рейд на i-го босса

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

Выходные данные должны содержать M чисел: ci  — минимальные затраты на покупку вещей для похода на i-го босса

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

Ограничения

1 ≤ N ≤ 5 ⋅ 104

1 ≤ M ≤ 5 ⋅ 104

1 ≤ ai, bi ≤ 109

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

Стандартный вход Стандартный выход
1
6 5
1 4 5 7 7 8
3 5 16 25 33
5 5 17 32 -1
2
10 8
10 20 30 40 50 60 70 80 90 100
1 2 9 10 550 551 151 150
10 10 10 10 550 -1 210 150

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

Автор:М. Спорышев, А. Кленин   Ограничение времени: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

Задача 8C. Наилучшее обучение

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

Условие

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

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

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

Первая строка входного файла содержит три целых числа a, n и b, разделенные пробелами.

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

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

Ограничения

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача Баллы Ограничения
anb
1601 ≤ a ≤ 1031 ≤ n ≤ 1031 ≤ b ≤ 109
2401 ≤ a ≤ 1061 ≤ n ≤ 1091 ≤ b ≤ 1018

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

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

Задача 8D. Автобусы

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

Условие

Перевозка пассажиров происходит по следующему алгоритму: автобус приходит на вокзал и ожидает пассажиров, пока они не займут все M мест. Новый автобус приходит на вокзал каждые d минут, первый автобус приезжает в момент времени 0. Время ожидания пассажира  — это время, пока он стоит на остановке (если автобус стоит на остановке, а пассажир находится в нём, это не считается за ожидание).

Перевозчику пришли новые требования к перевозке пассажиров: теперь суммарное время ожидания для всех пассажиров не должно превышать T минут.

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

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

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

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

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

Ограничения

0 ≤ N, M ≤ 106; 1 ≤ ti ≤ 106; 1 ≤ T ≤ 109

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача Баллы Дополнительные ограничения
NMtiT
1501 ≤ N ≤ 1031 ≤ M ≤ 1031 ≤ ti ≤ 1031 ≤ T ≤ 103
1501 ≤ N ≤ 1061 ≤ M ≤ 1061 ≤ ti ≤ 1061 ≤ T ≤ 109

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

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

6
2
6 3 6
6 6 6 6 6 6
8

Задача 8E. Большой линейный коллайдер

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

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e − , либо положительно заряженную частицу — позитрон e + . В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e −  частицы перемещаются по направлению уменьшения координаты, а e +  частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы e −  и e +  оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали m различных моментов времени t1, t2, ..., tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.

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

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

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (x1 < x2 < x3 < ... xn). Частица e −  описывается значением vi =  − 1, а частица e +  описывается значением vi = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t1,t2,...,tm.

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

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

 − 109 ≤ xi, m ≤ 109

0 ≤ ti ≤ 109

vi равно  − 1 или 1

Описание подзадач и системы оценивания

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

Подзадача Баллы Ограничения Необходимые подзадачи
nximti
1351 ≤ n ≤ 100 − 100 ≤ xi ≤ 100m = 10 ≤ ti ≤ 100
2121 ≤ n ≤ 100 − 109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091
3121 ≤ n ≤ 200 000 − 109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091, 2
4411 ≤ n ≤ 200 000 − 109 ≤ xi ≤ 109 1 ≤ m ≤ 200 0000 ≤ ti ≤ 1091, 2, 3

Получение информации о результатах окончательной проверки

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

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

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e +  в точке  − 1, частица e −  в точке 0, частица e +  в точке 1 и частица e −  в точке 5.

В момент времени 0.5 первая частица e +  и первая частица e −  сталкиваются в точке с координатой  − 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

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

Входной файл (linear.in) Выходной файл (linear.out)
1
4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3
4
2
0
0

Задача 98A. Баскетбол

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

Условие

Тимофей с одноклассниками обожают играть в баскетбол и не пропускают ни одной возможности сыграть в эту замечательную игру. Вот и сегодня на большой перемене состоялась важная игра (за выход в 1/1024 финала Объединенного городского школьного турнира).

Игра начинается со счета 0:0. Каждая результативная атака может принести одной из двух команд 1, 2 или 3 очка.

Введем понятие "ход игры" — последовательность изменения счета на табло. Например, ход игры может быть таким: 0-0, 2-0, 2-1, 5-1, 5-3.

Когда учитель информатики по пути в учительскую заглянул в спортзал, счет на табло был a:b. А после звонка на урок был зафиксирован окончательный результат — счет c:d. Теперь на уроке информатики перед ребятами поставлена задача — определить, сколько существует ходов игры, в которых:

1) Начальный счет — 0:0;

2) Промежуточный счет — a:b;

3) Окончательный счет — c:d.

Помогите Тимофею и его одноклассникам!

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

В первой строке входного файла через пробел записаны два числa: a и b — промежуточный счет. Во второй строке входного файла через пробел записаны два числa: c и d — окончательный счет.

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

Выведите одно натуральное число — количество различных ходов игры. Гарантируется, что ответ на задачу при любых входных данных не превосходит 1018.

Ограничения

0 ≤ a ≤ c ≤ 20 и 0 ≤ b ≤ d ≤ 20

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: a = 0, b = 0, c = 0, баллы: 15.

Подзадача 2: a = 0, c = 0, баллы: 15.

Подзадача 3: a = 0, b = 0, c = 1, баллы: 20.

Подзадача 4: a = 0, b = 0, баллы: 20.

Подзадача 5: нет ограничений, баллы: 30.

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

Комментарий ко второму примеру:

Комментарий к третьему примеру:

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

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

Problem 98B. Hall of water life

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

Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x1, …, xN from the hall entrance (xi < xi + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

  1. the first and the last aquariums should be left in their places;
  2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

Input file format

Input file contains integers N M followed by N integers xi.

Output file format

Output file should contain a single integer — the smallest possible maximum distance.

Constraints

2 ≤ N ≤ 400, 1 ≤ xi ≤ 109,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 2
1 2 3 4 5
2
2
4 1
10 21 30 40
19

Задача 98C. Рассадка пассажиров

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

Условие

Илон Маск закончил создание транспорта будущего — Hyperloop. Hyperloop — расположенный на опорах надземный трубопровод, внутри которого с высокой скоростью в одном направлении перемещаются одиночные транспортные капсулы. Пассажирский вариант предполагает n рядов по одному сиденью. Однако из-за конструктивных недостатков люди не могут сидеть на двух подряд идущих рядах. Поэтому, когда продаётся билет с номером места ai из продажи исчезает сам этот билет, и два соседних с ним билета.

Слон Пахом подрабатывает контролёром на Hyperloop. На рейс уже распродано k билетов с номерами ai. Так как все хотят прокатиться на Hyperloop, вы точно знаете, что все билеты будут распроданы. После продажи k билетов вам стало интересно, сколько существует различных способов продажи оставшихся билетов так, чтобы не нарушить правила продажи билетов. Способы считаются различными, если в одном из них существует хотя бы один билет, не проданный в другом.

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

Первая строка входного файла содержит два целых числа N и K. Далее следует K строк содержащих по одному числу ai. Гарантируется, что для всех пар i и j выполняется условие |ai − aj| ≥ 2 .

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

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

Ограничения

1 ≤ N ≤ 106; 1 ≤ K ≤ 105; 1 ≤ ai ≤ N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача Баллы Дополнительные ограничения
NK
1151 ≤ N ≤ 105, N - чётноеK = N / 2
2351 ≤ N ≤ 201 ≤ K ≤ 10
3501 ≤ N ≤ 1061 ≤ K ≤ 105

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

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

Задача 98D. Конкурс ТИК

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

Условие

Тимофей очень любит участвовать в разнообразных игровых конкурсах для школьников. "Китайская панда — иероглифы для всех", "Кентавр", "Французский пудель", "Золотой урон", "Сумчатое — аборигенам" — он не пропускает ни одного. Но особенно Тимофею нравится конкурс по технологии информационной коммуникации (ТИК).

Участникам конкурса ТИК предлагается ответить на n вопросов. На каждый вопрос предлагается четыре варианта ответа, обозначенных буквами a, b, c и d. Участник выбирает один из вариантов и отмечает его крестиком в поле для ответа. Правильный ответ на вопрос приносит конкурсанту один балл, неправильный — ноль баллов. Всего в конкурсе можно набрать от 0 до n баллов.

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

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

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

В первой строке входного файла записано одно натуральное число n — количество вопросов.

Во второй строке записаны верные ответы на вопросы конкурса — строка из n символов. На каждой позиции в строке стоит одна из четырех букв: a, b, c или d.

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

В единственной строке выходного файла запишите одно натуральное число — максимальное количество баллов, которое может набрать Тимофей в соответствии со Стратегией.

Ограничения

1 ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: n = 2, баллы: 15.

Подзадача 2: n ≤ 8, баллы: 30.

Подзадача 3: нет дополнительных ограничений, баллы: 55.

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

Комментарий к первому примеру:

Единственный вариант заполнения в соответствии со Стратегией, который даст возможность Тимофею получить 3 балла из 4: baba.

Комментарий ко второму примеру:

Один из вариантов заполнения в соответствии со Стратегией, который даст возможность Тимофею получить 3 балла из 8: abcbabcb. Больше 3 баллов набрать невозможно.

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

Стандартный вход Стандартный выход
1
4
daba
3
2
8
adbcaadb
3

Задача 98E. В чужом пиру - похмелье

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

Условие

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

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

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

Единственная строка входного файла содержит три натуральных числа, записанных через пробел: n, k и q — количество рыцарей на королевском пиру, а также любимые числа короля и королевы.

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

Выведите титул победителя — "King" или "Queen" (без кавычек).

Ограничения

1 ≤ k, q, n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при k = q, получат не менее 20 баллов.

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

На пиру 13 рыцарей. Любимое число короля — 6, королевы — 4. Первым ходом король хвалит 6 рыцарей. После любых ответных ходов королевы ему нужно хвалить по одному рыцарю. Если же король первым ходом восславит одного рыцаря, то он проиграет.

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

Стандартный вход Стандартный выход
1
13 6 4
King

Задача 99A. Подарок

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

Условие

Тимофей очень любит числа, являющиеся точными степенями двойки и тройки. У него даже есть два альбома, в которых хранятся карточки с этими числами: в первом можно найти 1, 2, 4, 8, 16 и так далее, а во втором — 1, 3, 9, 27 и так далее.

Тимофей хочет подарить папе число n, составленное из суммы чисел на этих карточках. Поскольку ему жалко расставаться со своими числами, он хочет подарить папе наименьшее число своих карточек, числа на которых в сумме дают n. Сколько карточек Тимофей подарит папе?

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

Единственная строка входного файла содержит одно натуральное число n.

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

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

Ограничения

1 ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 40 баллов.

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

В первом примере число два можно составить двумя способами: 1 + 1 или 2. Тимофей выберет второй способ и передаст папе одну карточку с двойкой.

Во втором примере есть способ (не единственный) представить число 79 в виде набора из четырех карточек: 79 = 64 + 9 + 4 + 2. Меньшим набором карточек обойтись нельзя.

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

Стандартный вход Стандартный выход
1
2
1
2
79
4

Задача 99B. Лабиринт

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

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

Во первой строке входного файла содержатся числа N, x0, y0, x1, y1. Далее следуют N строк по N символов в каждой — описание лабиринта.

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

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

Ограничения

0 ≤ N ≤ 100

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

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

Задача 99C. Наибольшая возрастающая подпоследовательность

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

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

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

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

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

Ограничения

1 ≤ N ≤ 100000;  − 109 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
123 456 124 124 125
3
1 4 5

Задача 99D. Свинья-копилка

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

Условие

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

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

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

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

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Ci Wi. Все числа во входном файле — целые.

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

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

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1

3.180s 0.012s 127