Задача 01A. Дошкольная сортировка ≡

Условие

Когда юному программисту Васе было три года, он уже знал, что буквы бывают "маленькие" (a, b, c, ..., z) и "большие" (A, B, C, ... Z), но ещё не выучил порядок букв в алфавите.

Мама играла с Васей в игру: она выписывала последовательность маленьких и больших букв, и спрашивала, "в порядке ли они". Если в последовательности шли сначала только маленькие буквы, а потом только большие, Вася отвечал YES (как будущий программист, он уже начал учить английские слова). Если в последовательности маленькие и большие буквы были перемешаны, Вася отвечал NO.

Напишите программу, которая будет действовать как Вася.

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

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

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

Выходной файл должен содержать строку YES, если все маленькие буквы в исходной строке расположены левее всех больших, либо строку NO в противном случае.

Ограничения

Длина входной строки от 1 до 10 символов.

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

maMA

YES

pRograMma

NO

zzzz

YES

AA

YES

Задача 01B. Построение солдат - 2 ≡

Условие

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

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

Ограничения

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

3
1.75 name1
1.70 name2
1.76 name3
    

2
    

Задача 01C. Передовики производства ≡

Условие

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

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

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

Ограничения

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

3 4
7 4 9 
2 3
1 4
2 10
2 -10

9
11
17
11

Problem 01D. ACM Rank Table ≡

Statement

ACM contests, like the one you are participating in, are hosted by the special software. That software, among other functions, preforms a job of accepting and evaluating teams' solutions (runs), and displaying results in a rank table. The scoring rules are as follows:

1. Each run is either accepted or rejected.
2. The problem is considered solved by the team, if one of the runs submitted for it is accepted.
3. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted run for this problem (in minutes) plus 20 minutes for every other run for this problem before the accepted one. For an unsolved problem consumed time is not computed.
4. The total time is the sum of the time consumed for each problem solved.
5. Teams are ranked according to the number of solved problems. Teams that solve the same number of problems are ranked by the least total time.
6. While the time shown is in minutes, the actual time is measured to the precision of 1 second, and the the seconds are taken into account when ranking teams.
7. Teams with equal rank according to the above rules must be sorted by increasing team number.

Your task is, given the list of N runs with submission time and result of each run, compute the rank table for C teams.

Input file format

Output file format

Constraints

Sample tests

2 3
1 1 5000 0
1 1 500 1
2 1 10000 1

1 2

3 3
1 2 3000 0
1 2 3100 1
2 1 4200 1

2 1 3

Задача 01E. Быстрая помощь ≡

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

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

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

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

Ограничения

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

2 10
8 5

25

Задача 01E. Хоттабыч и гирлянда ≡

Условие

Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку. Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из N цветных лампочек. Приглядевшись, Хоттабыч насчитал K различных цветов лампочек.

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

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

• K ≤ 2
• N ≤ 100

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

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

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

В N + 2-й строке входного файла содержится число M.

В последующих 2 * M строчках содержатся запросы Хоттабыча (по две строки на запрос).

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

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

Если в запросе указан цвет, отсутствующий на гирлянде, то в качестве ответа следует вывести  − 1.

Если лампочки обоих цветов есть, но пару найти невозможно, следует вывести  − 2.

Ограничения

2 ≤ N ≤ 15000

1 ≤ M ≤ 20000

1 ≤ K ≤ 3000

Строка, задающая цвет, состоит из латинских букв, её длина не превышает 255 символов.

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

10
Red
Green
Blue
Red
Brown
Green
Yellow
Black
Green
Red
6
Red
Green
Blue
Brown
Yellow
Green
Red
Black
Black
Blue
Orange
Green

0
1
0
1
4
-1

10
B
C
D
F
G
E
R
C
A
G
3
C
G
R
B
E
E

1 5 -2

Problem 01F. Bucket sort (LETTERS ONLY) ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Задача 02A. Золотая середина ≡

Условие

Центральным элементом набора из 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

Задача 02B. Силовые поля ≡

Условие

В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.

Экспериментальная установка содержит квадратную платформу размером 10⁹ × 10⁹, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (x_i, y_i).

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

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

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

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

Последующие n строк содержат по два целых числа x_i, y_i — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.

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

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

Ограничения

1 ≤ k ≤ n ≤ 200 000, 1 ≤ x_i, y_i ≤ 10⁹

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

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

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

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

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

На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.

Рис 1. Силовые поля в примере описания входных данных.

Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.

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

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

9

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

Условие

Дана последовательность из 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

Problem 02D. Game with rectangles ≡

Statement

Vasya writes a 2D game engine. One of the tasks is to determine parts of the scene visible by the gamer from a given position.

Let us consider a set of rectangles with sides parallel to the coordinate axes: P_i = {(x, y): a_i ≤ x ≤ b_i, c_i ≤ y ≤ d_i}.

Rectangle P_i is visible from the point A, if there exists some point B ∈ P_i such that segment AB does not contain points belonging to other rectangles.

Your program must determine indices of rectangles that are visible from the point (0, 0).

Input format

Input contains integer n followed by 4 × n integers: a_i, b_i, c_i and d_i.

Output format

Output must contain indices of visible rectangles in ascending order. Indices start from 0.

Constraints

Rectangles do not intersect each other and do not contain point (0, 0).

2 ≤ n ≤ 10⁵

 − 10⁶ ≤ a_i ≤ b_i ≤ 10⁶

 − 10⁶ ≤ c_i ≤ d_i ≤ 10⁶

Sample tests

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

0
2
3

5
 0  4  3  7
-1  2  1  2 
 1  5 -3 -2
 0  0 -6 -5
 0  0 -4 -2

1
2
4

Задача 03A. Сбалансированное дерево ≡

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача 03B. Сравнения подстрок ≡

Условие

Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a… b] и [c… d].

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

Сперва строка S из строчных латинских букв. Далее число M — количество запросов.

В следующих M строках по четыре целых числа — запросы a, b, c, d.

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

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

Ограничения

0 ≤ M ≤ 10⁵, 1 ≤ a ≤ b ≤ |S|, 1 ≤ c ≤ d ≤ |S|, 1 ≤ |S| ≤ 10⁵.

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

trololo
3
1 7 1 7
3 5 5 7
1 1 1 5

Yes
Yes
No

Задача 03C. Камень, ножницы, бумага и другие ≡

Условие

Глеб и Вася, студенты Института математики и компьютерных наук ДВФУ, часто играют в игру "камень, ножницы, бумага", чтобы определить, кто пойдёт мыть тряпку для стирания с доски.

Правила этой игры таковы: участники произносят фразу "камень, ножницы, бумага раз, два, три", после чего каждый участник показывает рукой один из трёх предметов: камень, ножницы или бумагу. В игре считается, что камень ломает ножницы, ножницы режут бумагу, бумага накрывает камень. Если, например, Глеб выбрал бумагу, а Вася выбрал ножницы, то Вася побеждает, а если оба игрока выбрали камень, то объявляется ничья.

Однажды Глеб и Вася захотели обобщить игру "камень, ножницы, бумага". Теперь в игре задействовано N предметов. Задаётся список пар предметов. Считается, что если один игрок выбрал первый предмет из некоторой пары, а другой игрок — второй предмет из этой пары, то тот, кто выбрал первый предмет из пары, побеждает. Если игроки выбрали пару предметов, которая не встречается в списке пар, то объявляется ничья.

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

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

1 ≤ M, K ≤ 200

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

Первая строка входного файла содержит целое число N — количество предметов. Далее следуют N строк — названия предметов. Длина названия составляет от 1 до 20 символов. Названия состоят из маленьких латинских букв. Все названия различны.

Следующая строка содержит целое число M — длину списка пар предметов. Далее следуют 2 × M строк — пары предметов. В каждой из этих строк может содержаться только название предмета из списка предметов. Никакие два предмета не могут содержаться одновременно в двух парах.

Следующая строка содержит целое число K — количество игр. Далее следуют 2 × K строк. В каждой из этих строк может содержаться только название предмета из списка предметов.

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

Выходной файл должен содержать K чисел. Для каждой игры должно быть выведено число 1, если выиграл первый игрок, число 2, если выиграл второй игрок, и число 0, если игроки сыграли вничью.

Ограничения

2 ≤ N ≤ 1000

1 ≤ M, K ≤ 20000

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

3
kamen
nozhnitsy
bumaga
3
kamen
nozhnitsy
nozhnitsy
bumaga
bumaga
kamen
2
bumaga
nozhnitsy
kamen
kamen

2 0

Задача 03D. Список школ ≡

Условие

При регистрации на портале интернет-олимпиады все участники заполняют регистрационную форму, где они указывают название школы, в которой они учатся. Разные участники могут по-разному писать название школы, например, "Физико-математическая школа №18", "ФМШ №18".

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

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

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

В приведенном примере для участия в интернет-олимпиаде зарегистрировались: два ученика из школы с номером 18, один ученик из школы с номером 42 и шесть учеников из школы с номером 9. Таким образом, от 1 до 5 участников зарегистрировано от школ с номерами 18 и 42.

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

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

Частичные правильные решения для тестов, в которых номера школ –- это числа строго меньше 1000, будут оцениваться из 50 баллов.

Частичные правильные решения для тестов, в которых номера школ –- это числа строго меньше 10⁹, будут оцениваться из 80 баллов.

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

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

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

Последующие n строк содержат названия школ, указанные участниками.

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

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

Ограничения

1 ≤ n ≤ 1000

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

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

9
Physics and Mathematics School 18
9ya shkola imeni Pushkina
Lyceum 9
PaMS 18
Gymnasium 42
School 9
Shkola nomer 9
High school 9
School N 9

2
18
42

Problem 03E. Compression research ≡

Statement

Many compression algorithms are based on finding frequently repeating substrings in the input data. Since it is often impractical to search the whole input for repetitions, only a limited compression window is considered on each step.

While researching a new compression algorithm, young computer scientist Vasya encountered the following problem.

Given input string of N bits, let the compression window be any substring of M bits. Inside each compression window, find the maximum number of occurrences of any substring of length L (L ≤ M).

In the sample input 1 below, compression window length is equal to string length, so there is only a single window. Most frequent substring of length 2 is 01, which occurs 5 times.

Input file format

First line of input file contains integers L M. Second line input file contains a string of length N, each character either 0 or 1.

Output file format

Output file must contain N − M + 1 integers — maximum substring frequencies for each compression window.

Constraints

1 ≤ M ≤ N ≤ 2 × 10⁵, 1 ≤ L ≤ 100

Sample tests

2 10
0101010101

5

1 3
1110000

3 2 2 3 3 

Задача 04A. Перестановки ≡

Условие

Во входном файле задано число n (1 ≤ n ≤ 8). Выведите в выходной файл в лексикографическом порядке все перестановки чисел от 1 до n.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 8).

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

Ограничения

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

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Задача 04B. Двоичные последовательности ≡

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

• рекурсивным перебором
• прибавлением 1 к числу в двоичной системе счисления

Да пребудет с тобой произведение массы на ускорение!

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

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

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

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

Ограничения

1 ≤ N ≤ 15

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

2

00
01
10
11

Задача 04E. Комбинированная эстафета ≡

Условие

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

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

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

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

Входной файл состоит из четырёх строк по четыре числа в каждой. j-ое число в i-ой строке (обозначим его t_ij) означает время, за которое i-ый спортсмен проходит дистанцию j-ым стилем. Каждое из чисел t_ij задано не более чем с двумя знаками после десятичной точки.

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

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

Ограничения

0 ≤ t_ij ≤ 120

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

49.61 55.47 61.97 53.33
53    59.5  66.5  57.5
56    63    70    61
59.5  67.5  75    65

3 2 4 1 

Задача 05A. Блинчики ≡

Условие

Мальчик Петя решил приготовить маме подарок на день рождения — праздничный завтрак. Он решил сделать вкусный чай и испечь блинчики. К сожалению, не отличаясь выдающимися кулинарными способностями, Петя не смог уследить за блинчиками. Каждый из них получился подгорелым с одной стороны и недожаренным с другой. В результате у Пети получилось N черно-белых блинчиков. Все блинчики он выложил на большую тарелку друг на друга. Теперь Петя хочет перевернуть их так, чтобы все они лежали светлой стороной вверх — Петя думает, что так они маме понравятся больше. Для переворачивания блинчиков у него есть лопаточка, которой он может взять несколько верхних блинчиков (от одного до всей стопки) и перевернуть их все вместе (таким образом, что верхний блин окажется на месте нижнего из взятых блинов).

За какое минимальное число таких действий Петя может перевернуть все блины светлой стороной вверх?

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

В первой строке входного файла дано число N (1 ≤ N ≤ 100 000) — количество блинчиков. Далее в N строках описываются блинчики, сверху вниз. Если в i-й строке стоит символ W, то i-й блинчик лежит недожаренной стороной вверх, а если B, то подгоревшей стороной вверх.

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

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

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

6
W
B
B
B
W
B

4

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача 05C. Опять лифт ≡

Условие

Высокое здание, состоящее из N этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от 1 до N снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна A_i. Известно, что лифт не может перевозить более C человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется P секунд. Какое наибольшее количество человек лифт может перевезти на парковку за T секунд, если изначально он находится на уровне парковки?

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

В первой строке входного файла содержатся целые числа N, C, P, T (1 ≤ N ≤ 100, 1 ≤ C ≤ 10⁹, 1 ≤ P ≤ 10⁹, 1 ≤ T ≤ 10⁹). Вторая строка содержит последовательность N целых чисел A₁, A₂, …, A_N (0 ≤ A_i ≤ 10⁹). Сумма всех значений последовательности не превосходит 10⁹.

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

Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.

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

4 5 2 15
0 1 2 3

3

Задача 05D. Сборка по степеням ≡

Условие

На днях в Логландии прошла вселогландская олимпиада школьников по математике. Мальчик Влад не смог пройти на заключительный этап этой олимпиады, но его очень заинтересовала одна задача c финала. Суть данной задачи следующая: дан отрезок целых чисел от 1 до n, необходимо определить количество различных чисел, которое можно представить в виде суммы одной или более неповторяющихся степеней k (т. е. чисел k¹, k², k³ и т. д.)

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

1 ≤ k ≤ 20

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

В первом примере мы может образовать из чисел 1, 3, 9, 27 следующие варианты: 1, 3, 4, 9, 10, 12, 13, 27, 28, 30.

Во втором примере мы можем представить все числа от 1 до 7.

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

30 3

10

7 2

7

Задача 05E. Limited permutation ≡

Условие

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

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

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

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

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

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

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

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

Ограничения

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

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

5
1 9 3 7 5
9 3 9 1 9

5 3 7 1 9

5
1 9 3 7 5
9 3 3 1 7

-1

Задача 06A. Любители SMS ≡

Условие

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

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

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

Расположение клавиш и координаты их центров показаны на приведённой схеме:

  1 2 3   (1; 1) (1; 2) (1; 3)
  4 5 6   (2; 1) (2; 2) (2; 3)
  7 8 9   (3; 1) (3; 2) (3; 3)
    0            (4; 2)
  

Одному члену жюри требуется набрать сообщение, состоящее из N символов. Помогите ему оценить минимальное время, которое для этого потребуется. Клавиша, которую нужно нажать, чтобы ввести i-й символ сообщения, задаётся изображённой на ней цифрой a_i. В начальный момент времени палец левой руки находится на клавише 4, а палец правой руки — на клавише 6.

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

• Минимизация расстояния на каждом шаге ведёт к минимизации ответа (жадный алгоритм)
• 1 ≤ N ≤ 20

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

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

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

Выходной файл должен содержать единственное вещественное число t — минимальное время набора сообщения. Абсолютная ошибка ответа не должна превышать 10^− 3.

Ограничения

1 ≤ N ≤ 10⁵, 0 ≤ a_i ≤ 9

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

4
1 3 2 7

5

6
5 2 9 0 0 3

6.650281540

Задача 06B. Новая система ≡

Условие

Утенок Даки на киникулах придумал новую систему для измерения времени и решил внедрить ее в своем университете. С помощью нее Даки предложил определять момент окончания лекций.

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

К концу лекции оба таймера должны закончить свою работу. Лекция длится T минут.

По заданным a, b и T определите искомую последовательность перезапусков.

Считается, что профессор перезапускает часы мгновенно.

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

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

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

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

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

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

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

Первая строка каждого блока должна содержать количество действий, k. Далее должно следовать k строк с парами целых чисел t_i m_i в каждой, где t_i — время выполнения действия, m_i — одно из чисел 1, 2 или 3, обозначающее, что необходимо перезапустить первый, второй или оба таймера соответственно. Для первого действия должно быть t_i = 0, для остальных t_i должно быть таким, что в этот момент песок хотя бы в одних часах только что полностью пересыпался вниз. Все t_i должны быть различны и расположены по возрастанию.

Для каждого теста выведите такой ответ, в котором количество действий не превосходит 500. Гарантируется, что в каждом тесте такой ответ существует.

Примечание: Поскольку блоки в выходном файле находятся один за другим, то, если указать неверное k в начале блока, все последующие блоки будут восприняты как ошибочные. Поэтому в случае частичного решения задачи рекомендуется указывать k = 0 для тех тестов, ответ к которым вам найти не удалось.

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

2
11 4 7
7 4 7

2
0 1
4 2
1
0 3

Задача 06D. Унисон ≡

Условие

Два друга-ирландца Фаолан и Леон очень любят петь, особенно в праздники, когда они могут собраться и петь песни вместе. Хоть они и друзья, у них не так много общих песен, но это не мешает им пытаться петь разные песни одновременно.

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

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

Когда Фаолан и Леон поют, они следуют по текстам своих песен слева направо, сверху вниз, с удовольствием распевая в унисон совместимые строки и пропуская все остальные.

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

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

В первой строке входных данных содержатся целые числа N M: количество строк в первой и второй песне соответственно. Далее следуют N + M строк, содержащих текст первой и затем второй песни. Каждая строка может состоять только из печатных ASCII символов.

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

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

Ограничения

1 ≤ N, M ≤ 10⁶

N * M ≤ 10⁷

Длина каждой строки не превосходит 50.

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

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

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

3 4
It's funny how the war goes on
Without John, without our John
La la la la la, la la!
We're so young and so gone
Let's chase the dragon from our home
Ah ah from our home!
From our home

17

Задача 06E. Поездка на каникулах ≡

Условие

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

Поезд следует от станции 1 до станции N, делая остановку на каждой станции. В поезде K мест, пронумерованных от 1 до K. На поезд продаются билеты, каждый билет характеризуется тремя числами: S, T и A. Такой билет позволяет проехать от станции S до станции T на месте A.

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

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

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

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

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

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

Каждая строка содержит три числа: s_i, t_i и a_i — номер станции, от которой куплен билет, номер станции, до которой куплен билет, и номер места, на которое куплен билет.

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

Далее идет строка, которая содержит число Q. Последующие Q строк содержат описания вариантов поездки. Каждая строка содержит два числа: f_j, d_j — номер станции, от которой Иван хочет поехать в этом варианте, и номер станции, до которой он хочет поехать.

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

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

Ограничения

2 ≤ N ≤ 200 000; 0 ≤ M ≤ 200 000, 1 ≤ K ≤ 200 000

1 ≤ s_i < t_i ≤ N; 1 ≤ a_i ≤ K

1 ≤ Q ≤ 200 000; 1 ≤ f_j < d_j ≤ N

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

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

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 2, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 1 и 2.

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

N ≤ 100; M ≤ 100; K ≤ 100, Q = 1

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

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q = 1

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

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q ≤ 200 000

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

По запросу сообщаются баллы за каждую подзадачу.

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

На перегоне от 2-й до 3-й станции все места заняты, поэтому проехать от 1-й до 5-й станции невозможно. От 3-й до 5-й станции можно проехать, используя два билета: от 3-й до 4-й станции на место 2 и от 4-й до 5-й на место 1. От 4-й до 5-й станции можно проехать, используя один билет на место 1.

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

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

-1
2
1

Задача 09A. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача 09B. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.

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

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

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

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

Ограничения

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

3 1
2 3

2

Problem 09C. Topological sorting ≡

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

Constraints

Sample tests

4 3
1 2
1 3
3 4

1 3 2 4

Problem 11A. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

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

0 5 7 17 -1

Problem 11B. Fast Dijkstra ≡

Statement

Input file format

Output file format

Constraints

Sample tests

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

0 5 7 17 -1

Problem 11C. Ford-Bellman ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3 1
1 2 5
1 3 10
2 3 2

0 5 7

Problem 11D. Biconnectivity ≡

Statement

Input file format

Output file format

Constraints

Sample tests

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

1 1

Problem 11E. Eulerian cycle ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2
2 3
3 1

1 2 3 1

Problem 14A. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Задача F3. Метро ≡

Условие

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

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

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

Во входном файле записано сначала число N — количество станций метро в городе. Далее записано число M — количество линий метро. Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

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

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

Ограничения

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

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

0

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

2

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

1

4 2
2 1 2
2 3 4
1 3

-1

Задача K1. Столицы ≡

Условие

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

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

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

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

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

В первом примере существует единственный способ выбрать три столицы: города с номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.

Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.

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

• Правильные решения для тестов, в которых 3 ≤ n ≤ 50, будут оцениваться из 20 баллов.
• Правильные решения для тестов, в которых 3 ≤ n ≤ 500, будут оцениваться из 40 баллов.
• Правильные решения для тестов, в которых 3 ≤ n ≤ 5000, будут оцениваться из 60 баллов.

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

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

Ограничения

3 ≤ n ≤ 10⁵, 1 ≤ d < n

1 ≤ a_i ≤ n, 1 ≤ b_i ≤ n, a_i ≠ b_i

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

4 2
1 2
1 3
1 4

1

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

5

Задача R0. Комментарии ≡

Условие

Джон, хотя и пишет на языке С, дает файлам расширение CPP, чтобы использовать в своих программах комментарии в С++-стиле (от // до конца строки). Обычный С-комментарий, который начинается с символов "/*" и заканчивается символами "*/", Джон также иногда использует, обычно для многострочных комментариев. Для участия в конкурсе программ необходимо, чтобы программа соответствовала стандартам языка ANSI С, и Джону нужно заменить все C++-комментарии на стандартные. Для этого в C++-комментарии можно заменить "//" на "/*" и добавить "*/" в конце строки. Иногда в C++-комментарии может встретиться последовательность символов "*/", в этом случае нужно вставить пробел между двумя этими символами: "* /". К счастью внутри строковых констант в программе Джона не встречаются последовательностей "//", "/*" и "*/".

Напишите программу, которая преобразует в программе Джона C++-комментарии в C-комментарии.

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

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

Ограничения

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

#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( //Печать
      "Hello, world");
  return 0; //*/*
}

#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( /*Печать*/
      "Hello, world");
  return 0; /** /**/
}

Задача R1. Правильная запись номера ≡

Условие

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

Российский телефонный номер в международном формате выглядит следующим образом: +7␣код_региона␣локальный_номер. В зависимости от длины кода региона существует 4 допустимых варианта записи:

• +7␣123␣123-45-67
• +7␣1234␣12-34-56
• +7␣12345␣1-23-45
• +7␣123456␣12-34

Сотрудник отдела кадров НИИ АСМ просит Вас написать программу, конвертирующую телефонный номер в международный формат.

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

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

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

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

Ограничения

Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона и локальный номер. Код региона — первый блок подряд идущих цифр после +7. В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45). Код региона может быть также обрамлён круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.

Суммарное количество цифр в коде региона и локальном номере равно 10. Длина входной строки не превышает 25 символов.

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

+7 (123)456-7-890

+7 123 456-78-90

+7(9876)543 210

+7 9876 54-32-10

+7-31415 92 - 65-3

+7 31415 9-26-53