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

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 1000

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

5

1 2

3

-1

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

Условие

Вася купил аллигатора и строку 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 ⋅ 10⁴ и не меньше чем 5, строка состоит из заглавных букв.

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

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

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

BOBIK

2

AYEAUEI

0

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

Условие

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

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

Ограничения

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

Longlongstring
2
short
string

0 1

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

Условие

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

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

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

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

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

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

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

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

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

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

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

1
30 6

0 0 0 0 6 0 

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

Условие

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

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

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

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

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

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

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ M < N ≤ 10⁵

 − 10⁴ ≤ a_i ≤ 10⁴

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

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

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

4 1
1 2 3 4

3 4 3

4 2
3 2 1 1

3 4

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

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ n, m, k_i ≤ 10⁵; 1 ≤ a_i ≤ 10⁹; 1 ≤ p_i ≤ 100

Сумма по всем k_i не превосходит 2 ⋅ 10⁵.

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

Решения работающие для 0 ≤ n, m, k_i ≤ 10³; 1 ≤ a_i, p_i ≤ 10³, сумма по всем k_i не превосходит 2 ⋅ 10³ оцениваются из 40 баллов.

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

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

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 ≡

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

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

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

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

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i < 2⁶⁴

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

2
12 16

4

2
25 9

1

3
12 27 15

3

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

Условие

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

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

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

Ограничения

1 ≤ A, B ≤ 2³¹ − 1

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

10 20

2

13 17

1

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

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 1000

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

1

2

3

2 3 5

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n, m, k ≤ 10⁹

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

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

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

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

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

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

729 1024 15

13

17 19 30

0

Задача 3E. Square coins ≡

Условие

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

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

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

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

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

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

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

Ограничения

8 ≤ n ≤ 10¹²

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

В примере дана стоимость монеты 72. Ей могут соответствовать три подходящих размера: 9² − 3² = 81 − 9 = 72, 11² − 7² = 121 − 49 = 72 и 19² − 17² = 361 − 289 = 72.

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

72

3
9 3
11 7
19 17

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

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ n ≤ 10⁶

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

5

120

1000000

641102369

0

1

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

Условие

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

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

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

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

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

Для каждого запроса выведите значение a^b по модулю 10⁹ + 7.

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁵

0 ≤ a, b ≤ 10⁹

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

3
3 4
2 8
123 123

81
256
921450052

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

Условие

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

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

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

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

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

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

Для каждого запроса выведите значение a^bc по модулю 10⁹ + 7.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ a, b, c ≤ 10⁹

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

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764

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

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ n_a, n_b, n_c ≤ 10⁵

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

1 1 1

6

2 2 5

756

100000 100000 100000

141974424

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

Условие

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

Смишенное произведение набора различных натуральных чисел a₁, a₂, …, a_n устроено следующим образом. Рассмотрим все возможные упорядоченные пары (a_i, a_j) различных чисел этого набора. Для каждой пары запишем эти числа подряд без пробела, получив новое число b_ij. Смишенным произведением чисел из исходного набора Миша называет сумму всех значений b_ij.

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

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

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

Вторая строка содержит n различных натуральных чисел a₁, a₂, …, a_n — числа набора.

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

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

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i ≤ 10⁸

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

3
1 3 10

668

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100000; 1 ≤ a_i ≤ 10⁹

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

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

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

N ≤ 100

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

N ≤ 5000

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

N ≤ 100 000

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

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

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

5
1 3 4 2 5

1 3 3 4 

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ K ≤ 100

1 ≤ N ≤ 10⁵

0 ≤ x_i ≤ 2 ⋅ 10⁵

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

6 1
1 1 4 5 8 0

-1

10 2
4 2 2 5 10 5 4 9 0 10

6

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

4 ≤ n ≤ 10¹⁰

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

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

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

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

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

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

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

4

1

16

2

10000

4

Задача 5D. Caterpillar ≡

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ a_i, N, L ≤ 10⁶, L ≤ N, a_i ≠ a_i + 1

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

1 4
4 3 2 3

1

3 10
10 9 8 7 8 9 10 9 8 7

4

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

Условие

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

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

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

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

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

Ограничения

2 ≤ |s| ≤ 10⁶

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

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

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

aabcb

3

abacaba

5

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 5 ⋅ 10⁴

1 ≤ M ≤ 5 ⋅ 10⁴

1 ≤ l_i ≤ r_i ≤ N

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

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

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

-1
1
-1
1

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. Призы ≡

Условие

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

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

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

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

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

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

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

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

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

3 ≤ n ≤ 50, 1 ≤ a_i ≤ 10⁵.

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

3 ≤ n ≤ 5000, 1 ≤ a_i ≤ 10⁵.

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

3 ≤ n ≤ 100000, 1 ≤ a_i ≤ 10⁹.

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

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

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

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

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

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

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

Ограничения

3 ≤ n ≤ 100000, 1 ≤ k ≤ n / 3, 1 ≤ a_i ≤ 10⁹.

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

10 2
1 2 4 5 2 4 2 2 1 6

7

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

Условие

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

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

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

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

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

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

Ограничения

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

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 ≡

Условие

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

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

• Найти разность между максимальным и минимальным значениями среди элементов a_i, a_i + 1, …, a_j.
• Присвоить элементу a_i значение j.

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

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

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

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

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

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

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

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

Ограничения

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

7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3

34
68
250
234
1

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

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

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

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

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

Условие

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

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

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

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

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

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

Ограничения

0 ≤ n, m ≤ 10⁹

1 ≤ w₁, h₁, w₂, h₂ ≤ 10⁹

w₁ ≤ h₁

h₂ ≤ w₂

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

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

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

Решения, верно работающие при w₁ = h₂, h₁ = w₂, получат не менее 20 баллов.

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

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

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

5 2 3 4 5 1

10

Задача 7C. New function ≡

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

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

448

404

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁸.

1 ≤ a, b, c, d ≤ 10¹⁵.

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

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

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

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

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

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

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

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

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

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

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

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

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

11 1 2 2 3

6

1 1 1 1 1

1

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ L, d ≤ 10⁹

0 ≤ c ≤ 10⁹

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

10 2 2

0

10 3 2

2

100 9 9

-1

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 5 ⋅ 10⁴

1 ≤ M ≤ 5 ⋅ 10⁴

1 ≤ a_i, b_i ≤ 10⁹

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

6 5
1 4 5 7 7 8
3 5 16 25 33

5 5 17 32 -1

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. Гаджет в кредит ≡

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

1 0 1

1

1 124 12

8

1 1 12

2

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

Условие

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

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

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

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

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

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

Ограничения

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

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

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

5 10 15

3

10 10 10

1

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

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ N, M ≤ 10⁶; 1 ≤ t_i ≤ 10⁶; 1 ≤ T ≤ 10⁹

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

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

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

5 3 3
5 4 3 2 1

6

6 3 6
6 6 6 6 6 6

8

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

Условие

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

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

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

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

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

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

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (x₁ < x₂ < x₃ < ...  < x_n). Частица e⁻ описывается значением v_i =  − 1, а частица e⁺ описывается значением v_i = 1.

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

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

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

Ограничения

1 ≤ n, m ≤ 200000

 − 10⁹ ≤ x_i, m ≤ 10⁹

0 ≤ t_i ≤ 10⁹

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

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

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

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

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

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

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

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

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

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

4
2
0
0

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

Условие

Тимофей с одноклассниками обожают играть в баскетбол и не пропускают ни одной возможности сыграть в эту замечательную игру. Вот и сегодня на большой перемене состоялась важная игра (за выход в 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 — окончательный счет.

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

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

Ограничения

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.

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

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

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

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

0 0
0 0

1

0 0
3 1

12

2 0
3 1

4

Problem 98B. Hall of water life ≡

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 x₁, …, x_N from the hall entrance (x_i < x_i + 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 x_i.

Output file format

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

Constraints

Sample tests

5 2
1 2 3 4 5

2

4 1
10 21 30 40

19

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁶; 1 ≤ K ≤ 10⁵; 1 ≤ a_i ≤ N

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

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

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

4 2
2
4

1

3 0

2

5 1
1

2

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

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

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

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

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

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

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

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

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

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

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

4
daba

3

8
adbcaadb

3

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ k, q, n ≤ 10⁵

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

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

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

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

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

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

13 6 4

King

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

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

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

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

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

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

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

2

1

79

4

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

Условие

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

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

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

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

Ограничения

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

4 1 1 4 1
..#.
..#.
..#.
....

9

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

Условие

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

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5

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

Условие

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

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

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

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

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

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

Ограничения

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

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

10 110 2
1 1
30 50

60

10 110 2
1 1
50 30

100

1 6 2
10 3
20 4

-1