Задача A. Лифты ≡

Условие

N людей хотят попасть на L этаж. Сейчас они находятся на нулевом этаже. Они могут воспользоваться лифтами, коих E штук. Вместимость каждого лифта равна V. Каждый лифт может двигаться вверх и вниз со скоростью один этаж в секунду. Пешком по лестнице человек поднимается на один этаж за T секунд. Вместимость лестницы бесконечна. Какое минимальное количество времени должна потратить эта группа людей, чтобы всем оказаться на L этаже?

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

Входные данные содержат пять целых чисел: N, L, E, V, T.

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

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

Ограничения

1 ≤ N ≤ 10⁹

1 ≤ L, E, V, T ≤ 10³

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

2 4 1 1 1

4

20 4 2 5 1000

12

Задача B. Карточный фокус ≡

Условие

Слон Пахом выучил карточный фокус и теперь показывает его всем. Суть фокуса в том, что слон должен отгадать карту, которую загадал игрок. Фокус выполняется следующим образом: берётся колода, состоящая из n карт, и совершается несколько итераций. На каждой итерации все карты раскладываются в m стопок по n / m карт в каждой. Пахом сам выбирает, как раскладывать карты. Далее игрок говорит, в какой стопке лежит карта, которую он загадал. Если слон Пахом уже может однозначно назвать карту, которую загадал игрок, то фокус заканчивается.

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

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

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

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

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

Ограничения

2 ≤ n, m ≤ 10⁹

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

4 2

2

30 5

3

10 10

1

Задача C. Контроль за выловом рыбы ≡

Условие

Всего для вылова доступно P видов рыб. Известно, что компания владелец рыболовного судна получила квоты на вылов w_i килограмм i-го вида рыбы.

Рыболовное судно выловило N рыб, i-я рыба имеет вес m_i. Каждая из выловленных рыб отнесена к одному из P видов.

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

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

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

Первая строка входного файла содержит целые числа P, N, K. Во второй строке содержится P целых чисел w_i — размер квоты в килограммах на вылов рыбы вида i. В третьей строке содержится N пар целых чисел m_i и t_i — масса и вид, к которому отнесли рыбу с номером i рыболовы.

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

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

Ограничения

1 ≤ N, P ≤ 10⁵, 0 ≤ K ≤ 10⁵, 1 ≤ w_i, m_i ≤ 10⁹, 1 ≤ t_i ≤ P

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

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

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

2 5 2
5 6
1 1 1 1 1 1 1 2 1 2

NO

2 2 1
3 6
3 1 6 2

YES

Задача A. Отбор ≡

Условие

Гриша участвует в отборе на стажировку в ***. Он не знает, на какой позиции он находится в таблице результатов, но знает, что в отборе участвует n претендентов. Кроме того, Гриша точно знает, что не менее a человек показали лучшие чем у Гриши результаты, и не более b человек написали отбор хуже, чем он.

Грише интересно количество позиций в итоговой таблице, которые он может занять.

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁴

0 ≤ a, b < n

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

3 1 1

2

5 2 3

3

Задача B. Генерация строки ≡

Условие

Требуется сгенерировать лексикографически минимальную строку состоящую из n букв "a", m букв "b" и k букв c. В искомой строке не должно быть двух подряд идущих букв "a", и для любых 4 подряд идущих букв должно встречаться не более одной буквы "c". На буквы "b" дополнительных ограничений нет.

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

Входного файл содержит 3 целых числа n, m, k в одной строке.

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

Выходной файл должен содержать искомую строку длины n + m + k если такая строка существует, в противном случае строку "NO".

Ограничения

0 ≤ n, m, k ≤ 10⁵, 1 ≤ n + m + k ≤ 10⁵

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

Решения работающие для n + m + k ≤ 10 оцениваются из 50 баллов. Решения для k = 0 оцениваются из 40 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

1 1 1

abc

10 3 1

NO

5 3 2

ababacabac

Задача C. Контроль за выловом рыбы ≡

Условие

Всего для вылова доступно P видов рыб. Известно, что компания владелец рыболовного судна получила квоты на вылов w_i килограмм i-го вида рыбы.

Рыболовное судно выловило N рыб, i-я рыба имеет вес m_i. Каждая из выловленных рыб отнесена к одному из P видов.

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

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

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

Первая строка входного файла содержит целые числа P, N, K. Во второй строке содержится P целых чисел w_i — размер квоты в килограммах на вылов рыбы вида i. В третьей строке содержится N пар целых чисел m_i и t_i — масса и вид, к которому отнесли рыбу с номером i рыболовы.

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

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

Ограничения

1 ≤ N, P ≤ 10⁵, 0 ≤ K ≤ 10⁵, 1 ≤ w_i, m_i ≤ 10⁹, 1 ≤ t_i ≤ P

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

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

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

2 5 2
5 6
1 1 1 1 1 1 1 2 1 2

NO

2 2 1
3 6
3 1 6 2

YES

Задача A. Марсианская лингвистическая реформа ≡

Условие

Алфавит марсианского языка состоит из строчных латинских букв. Буквам a, e, i, o, u, y соответствуют гласные звуки, остальным — согласные.

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

Марсиане просят написать программу, переводящую слова из старого в новый форматы.

Например, если старое слово имело вид eeaaeeuinfaormaaiatoyuaoics, то новое слово будет таким: eeaaeeuinfaormaaiatoyuaoics  ↦  informatics.

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

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

Ограничения

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

eeaaeeuinfaormaaiatoyuaoics

informatics

aeeaaayyaaauaaiaaiaacm

acm

bzzt

bzzt

Задача B. Марфа Геннадьевна и напёрстки ≡

Условие

Этим летом Марфа Геннадьевна побывала в Турции. Там она участвовала в усложнённой игре в напёрстки. Правила игры таковы. У ведущего есть три напёрстка, под каждым из которых находится шарик, то есть всего есть три шарика: маленький, средний и большой. Ведущий может несколько раз менять местами соседние напёрстки, после чего игроку предлагается отгадать, под каким напёрстком какой шарик находится.

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

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

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

Первая и вторая строки входного файла содержат по 3 целых числа от 1 до 3. Число 1 означает маленький шарик, 2 — средний, 3 — большой. В каждой строке все числа различны.

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

Требуется вывести в выходной файл единственное целое число — ответ в задаче.

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

1 2 3
3 2 1

3

2 1 3
2 1 3

0

3 1 2
3 2 1

1

Задача C. Выбор зала ≡

Условие

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

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

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

Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами Y × Z и Z × Y считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям.

Требуется написать программу, которая по заданным A, B, C и D определяет количество различных залов, площадь которых находится в пределах от A до B, а периметр — от C до D, включительно.

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

В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2.

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

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

1 ≤ A ≤ B ≤ 1000, 4 ≤ C ≤ D ≤ 1000.

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

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

1 ≤ A ≤ B ≤ 10⁹, 4 ≤ C ≤ D ≤ 10⁹.

В этой подзадаче 25 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

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

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

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

Входной файл содержит четыре разделенных пробелами целых числа: A, B, C и D.

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

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

Ограничения

1 ≤ A ≤ B ≤ 10⁹, 4 ≤ C ≤ D ≤ 10⁹

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

2 10 4 8

3

Задача D. Удаление чисел ≡

Условие

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

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

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

Например, пусть n = 13, k = 2.

• На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
• На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
• На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
• На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

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

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

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

Вторая строка входных данных содержит целое число k.

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

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Ограничения

3 ≤ n ≤ 10¹⁸

2 ≤ k ≤ 100, k < n

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

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

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

13
2

3

Задача E. Неисправный марсоход ≡

Условие

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

Мощность батареи марсохода задаётся целым положительным числом. Текущая мощность батареи равна a, для восстановления работоспособности марсохода необходимо повысить её мощность до значения b. Для изменения мощности батареи на марсоход с Земли можно передавать специальные сигналы двух типов: X и Y. Сигнал типа X увеличивает текущую мощность батареи на 1, а сигнал типа Y увеличивает текущую мощность батареи на 2.

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

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

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

Входные данные содержит три целых числа: a, b и c, по одному на строке.

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

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

Ограничения

1 ≤ a < b ≤ 10⁹, 2 ≤ c ≤ 10⁹, a не кратно c, b не кратно c

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

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

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

В первом примере можно действовать следующим образом: отправить на марсоход сигналы Y, X, Y. Мощность батареи меняется следующим образом: 2 ↦ 4 ↦ 5 ↦ 7.

Во втором примере можно действовать следующим образом: отправить на марсоход сигналы X, Y, X, Y. Мощность батареи меняется следующим образом: 4 ↦ 5 ↦ 7 ↦ 8 ↦ 10.

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

2
7
3

3

4
10
3

4

Задача F. Числовая последовательность ≡

Условие

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

Недавно руководитель отдела, где начал работать Дима, столкнулся с весьма интересной последовательностью чисел a₁, a₂, …, a_n, …, которая определяется следующим образом: a₁ = 0 и каждое последующее число a_i + 1 (i ≥ 1) определяется как наименьшее натуральное число, большее a_i, десятичная запись которого не содержит цифр, представленных в десятичной записи a_i. Требуется написать программу, которая заданному n вычисляет величину a_n.

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

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

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

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

Ограничения

1 ≤ n ≤ 500

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

1

0

28

911

Задача I. Болезнь ≡

Условие

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

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

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

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

В первой строке входного файла заданы два числа n (1 ≤ n ≤ 100) — число различных возбудителей болезни и m — число анализов. Следующие m (1 ≤ m ≤ 10 000) строк содержат по n + 1 числу. Первые n чисел описывают, какие возбудители обнаруживаются этим анализом, i-е число равно 1, если анализ проверяет наличие i-го возбудителя и 0 — в противном случае.

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

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

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

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

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

3 3
1 0 0 0
1 1 1 1
0 1 0 0

2 1 2
1 3
0

2 2
1 1 0
1 0 1

Incorrect

2 1
1 1 1

0
0
2 1 2

Задача A. Полоса препятствий ≡

Условие

Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены h_i.

Цель робота — преодолеть все стены, достать флаг, который находится в конце полосы за всеми стенами, и вернуться обратно. Стену можно преодолеть двумя способами: подняться, проплыть над ней и опуститься обратно или сделать подкоп. Если стена была преодолена с помощью подкопа, то в при проходе в обратную сторону можно воспользоваться уже готовым подкопом. Всего разрешается сделать не более m подкопов.

Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.

Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.

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

Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел h_i - высоты стен.

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

Выходной файл должен содержать строку NO, если задание выполнить невозможно. В противном случае — две строки: строку YES и строку из 2 n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n символов содержат описание прохождения от стены с номером n до стены с номером 1.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ n, m ≤ 10⁵, 1 ≤ k, h_i ≤ 10⁹

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

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

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

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

YES
DUDUDUUUDDDDUUUDUDUD

5 1 1
5 5 5 5 5

NO

10 10 10000
13123 141323 213323 3213 213213 321 323213 1323 213 1232113

YES
DDDDDDDDDDDDDDDDDDDD

Задача B. Зельеварение ≡

Условие

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

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

К сожалению, температура в комнате очень быстро стала некомфортной. И тут Вася подумал, почему бы не сделать температуру воздуха в комнате равной T₀ + K, где T₀ — температура в комнате до приготовления зелий. Он тут же вспомнил, что на уроках заклинаний он недавно научился заклинанию исчезновения! Заклинание позволяет ему безвозвратно уничтожить любой непрерывный отрезок подряд идущих колб вместе с их влиянием на температуру воздуха в комнате. Используя только это заклинание, Вася хочет сделать температуру в комнате желаемой.

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 10³

 − 10⁷ ≤ K ≤ 10⁷

 − 10⁴ ≤ a_i ≤ 10⁴

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

1 0
1

1

5 1
1 2 3 -1 -1

4

Задача C. Синхронизация ≡

Условие

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

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

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

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

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

Входной файл содержит целое число N. Далее следует N целых чисел a₁, a₂, …, a_N — времена событий, зафиксированных коллайдером. Затем записано целое число M. Далее следует M чисел b₁, b₂, …, b_M — времена событий, зафиксированных Колей.

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

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

Ограничения

2 ≤ M ≤ N ≤ 10⁵;

0 ≤ a₁ ≤ a₂ ≤ …  ≤ a_N ≤ 10⁹;

0 = b₁ ≤ b₂ ≤ …  ≤ b_M ≤ 10⁹;

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

5
10 15 17 19 20
2
0 2 

2

Problem D. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Задача A. Домино (классика) ≡

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

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

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

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

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

2 3

3

Задача B. Алфавитное сжатие ≡

Условие

Недавно компания TIoN разработала новый способ сжатия сообщений.

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

После выбора отрезка он заменяется на "*n.d", где '*' — первая буква отрезка, 'n' — количество букв в отрезке, 'd' — разница между каждой парой соседних букв. Например, отрезок "cdefghi" после сжатия будет выглядеть как "c7.1", а отрезок "geca" — "g4.-2".

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

Компании TIoN в срочном порядке необходимо доказать целесообразность существования нового вида сжатия. Для этого им нужно вычислить минимально возможную длину сообщения S после сжатия.

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

Первая строка содержит одно целое число N — длина сообщения.

Вторая строка содержит строку S — сообщение, которое подвергается сжатию.

Строка S состоит из строчных букв латинского алфавита.

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

Выведите одно целое число — минимальную длину сообщения после сжатия.

Ограничения

1 ≤ N ≤ 10⁵

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

В первом примере есть два варианта сжатия сообщения: "x10.0t5.-4" и "x9.0x6.-4". Второй вариант короче первого на 1 символ.

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

15
xxxxxxxxxxtplhd

9

7
cdefghi

4

4
geca

4

Задача C. Коммивояжёр возвращается! ≡

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

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

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

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

В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения a_ij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. a_ij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.

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

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

Ограничения

1 ≤ n ≤ 19, a_ij ≤ 10⁸

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

3
-1 1 6
3 -1 7
4 9 -1

5

4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1

3

Problem D. 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

Задача E. Доклад с картинками ≡

Условие

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

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

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

В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.

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

Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h₁… h_n.

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

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

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 10⁸;

1 ≤ h_i ≤ k;

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

4 10
4 6 4 6

4 4 6 6

Задача F. Не только динамика! Новые тесты! ≡

Условие

Дан набор a_i из N чисел. Необходимо расположить числа в последовательности a₁, a₂, …, a_N один за другим так, чтобы максимизировать следующую целевую функцию: (a₁ * a₂ + a₂ * a₃ + …  + a_N − 1 * a_N)

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

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

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

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

Ограничения

2 ≤ N ≤ 16

1 ≤ a_i ≤ 10⁶

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

4
9 1 9 2

108

Задача I. Реформа галактических вооруженных сил ≡

Условие

Армия галактического альянса состоит из 2 N дивизионов боевых дроидов. Верховное командование приняло решение сократить количество дивизионов вдвое, объединив их попарно. Объединение двух дивизионов происходит следующим образом: каждый из дивизион разбивается на одинаковое количество K_i отрядов дроидов, после чего отряды сливаются и формируют K_i увеличенных отрядов, составляющих новый объединенный дивизион.

Программное обеспечение дроидов поддерживает разбиение дивизиона дроидов только на равные по количеству отряды. Например, дивизион из 6 дроидов может быть разбит на 1 отряд из 6 дроидов, 2 отряда из 3 дроидов, 3 отряда из 2 дроидов или 6 отрядов из 1 дроида.

Считается, что после объединения двух дивизионов, максимальную эффективность в бою имеет объединенный дивизион с наибольшим количеством отрядов. Например, максимально эффективный способ объединить два дивизиона, состоящие из из 6 и 4 дроидов — это разбить каждый на два отряда по 3 и 2 дроида, соответственно. Затем сформировать два увеличенных отряда по 5 дроидов. Новый объединенный дивизион будет состоять из 10 дроидов, состоящих в 2 отрядах.

Рассмотрим армию, состоящую из 4 дивизионов: 4 9 3 6. Возможные варианты разбиения дивизионов на равные по численности отряды: 1 дивизион: 1 по 4, 2 по 2, 4 по 1. 2 дивизион: 1 по 9, 3 по 3, 9 по 1. 3 дивизион: 1 по 3, 3 по 1. 4 дивизион: 1 по 6, 2 по 3, 6 по 1.

Соответственно, оптимальным решением будет объединение дивизионом 1 и 4 с разбиением на 2 отряда каждого, а также дивизионов 2 и 3 с разбиением на 3 отряда каждого. Общее количество отрядов в армии после объединения — 5.

Требуется данные 2 N дивизионов дроидов попарно объединить таким образом, чтобы общее количество отрядов в армии было максимальным.

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

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

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

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

Ограничения

1 ≤ N ≤ 10; 1 ≤ D_i ≤ 10⁹

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

2
1 2 3 4

3

2
4 9 3 6

5

2
30 18 5 12

11

Задача J. Поход за шляпой ≡

Условие

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

Маша выбирает шляпу в несколько заходов. Заход номер i состоит из посещения отрезка бутиков с номерами от L_i до R_i (1 ≤ L_i ≤ R_i ≤ N). Маше нравится процесс выбора, поэтому она хочет сделать как можно больше заходов. Однако, чтобы не слишком сильно испытывать терпение Васи, она решила делать заходы по следующим правилам:

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

Например, для ряда из 5 бутиков с брендами caabb возможна такая последовательность заходов:

(1, 5), (1, 4), (2, 5), (3, 4), (2, 4), (3, 5), (4, 4), (4, 5), (5, 5).

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

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

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

За тесты c 1 по 20 начисляется по 2 балла, за остальные (с 21 по 40) по 3 балла.

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

Первая строка входного файла содержит целое число T — количество тестов. Далее идут T описаний тестов, по две строки на описание.

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

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

Выходной файл должен содержать T ответов на тесты.

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

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с числом 0.

Ограничения

Буквы брендов находятся в диапазоне от 'a' до 't'.

1 ≤ N ≤ 1000

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

2
2
aa
5
caabb

3
9

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

Условие

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

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

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

В первой строке входного файла содержатся числа 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

Задача B. Наибольшая общая подпоследовательность ≡

Условие

Найдите наибольшую общую подпоследовательность двух строк.

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

В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.

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

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

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

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

ababaca
acaba

aaba

Задача B. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

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

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

Далее следуют N пар целых чисел c_i a_i.

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

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

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

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

Условие

Илон Маск закончил создание транспорта будущего — 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

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

Условие

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

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5

Задача E. Алфавитное сжатие ≡

Условие

Недавно компания TIoN разработала новый способ сжатия сообщений.

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

После выбора отрезка он заменяется на "*n.d", где '*' — первая буква отрезка, 'n' — количество букв в отрезке, 'd' — разница между каждой парой соседних букв. Например, отрезок "cdefghi" после сжатия будет выглядеть как "c7.1", а отрезок "geca" — "g4.-2".

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

Компании TIoN в срочном порядке необходимо доказать целесообразность существования нового вида сжатия. Для этого им нужно вычислить минимально возможную длину сообщения S после сжатия.

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

Первая строка содержит одно целое число N — длина сообщения.

Вторая строка содержит строку S — сообщение, которое подвергается сжатию.

Строка S состоит из строчных букв латинского алфавита.

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

Выведите одно целое число — минимальную длину сообщения после сжатия.

Ограничения

1 ≤ N ≤ 10⁵

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

В первом примере есть два варианта сжатия сообщения: "x10.0t5.-4" и "x9.0x6.-4". Второй вариант короче первого на 1 символ.

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

15
xxxxxxxxxxtplhd

9

7
cdefghi

4

4
geca

4

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

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

Условие

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

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

• Первоначально сумма долга равна стоимости гаджета 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

Задача C. Вырубка леса ≡

Условие

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2 K-й, 3 K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2 M-й, 3 M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

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

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

• 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
• 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
• 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
• 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
• 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
• 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
• 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

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

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

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

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

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

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

1 ≤ X ≤ 10¹⁸; X < K; X < M.

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

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

1 ≤ X ≤ 10¹⁸.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 10¹⁸, 1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

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

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

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

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

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

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

Ограничения

1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸, 1 ≤ X ≤ 10¹⁸

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

2 4 3 3 25

7

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

Условие

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

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

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

В первой строке входного файла содержатся числа 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

Задача B. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

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

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

Далее следуют N пар целых чисел c_i a_i.

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

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

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

Задача A. Два компьютера ≡

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров T_i секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

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

Ограничения

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

5 7 10 3 5 6

16

Задача B. Автомобильные номера ≡

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

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

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

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

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

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача C. Имена файлов ≡

Условие

I wish we had some way to handle it sanely, but I don't think a sane solution to case-insensitivity exists.

Linus Torvalds

На компьютере под управлением операционной системы Linux имеется каталог, содержащий N файлов. Пользователю требуется скопировать эти файлы на компьютер, работающий под управлением ОС Windows. К сожалению, файловая система Windows имеет странное свойство. Несмотря на то, что она сохраняет большие и малые буквы в именах файлов, имена, отличающиеся только регистром букв, считаются одинаковыми. Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании на файловую систему Windows попадут в один и тот же файл.

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

1. Файлы копируются в порядке перечисления в исходном каталоге.
2. Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
3. Если при копировании очередного файла выяснилось, что файл с таким именем уже был скопирован, то к имени текущего файла добавляется суффикс "1".
4. Если имя, полученное после присоединения суффикса, также уже встречалось, то перебираются суффиксы "2", "3", ..., "10", "11", ... до тех пор, пока не найдётся суффикс, дающий уникальное имя.

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

Входной файл содержит количество имён N, за которым следует N строк с именами. Имена состоят из латинских букв и цифр и имеют длину от 1 до M символов.

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

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

Ограничения

1 ≤ N ≤ 10000, 1 ≤ M ≤ 255

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

4
aA
Aa
aa
AA1

aA
Aa1
aa2
AA11

Задача D. Восстановить IP ≡

Условие

Корректная запись IP-адреса — это строка, состоящая из четырёх десятичных чисел в диапазоне от 0 до 255 каждое, разделённых символом "точка" (ASCII 46). Компоненты записи IP-адреса не должны содержать лидирующих нулей.

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

Помогите Пете восстановить IP-адрес.

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

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

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

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

7.2
102.
47
84.1

102.84.17.247

.0.
00
1
2.0

100.0.2.0
2.0.0.100

Задача E. Ответы к тесту ≡

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

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

По этим данным Гена должен определить правильные ответы.

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

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

• В первой строке описываются ответы, данные шушанчиком. Они задаются строкой длинной Q, состоящей из символов + (ASCII 43) или - (ASCII 45) для ответов "Да" или "Нет" соответственно. На i-ой позиции строки находится ответ на i-ый вопрос.
• Во второй строке содержится целое число — количество баллов.

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

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

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

1 2
+-
0

-+

3 4
--++
3
----
1
---+
2

+-++

Задача A. Сумма ≡

Условие

Дан массив из 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

Задача B. Переворачивания ≡

Условие

Учитель физкультуры школы с углубленным изучением предметов уже давно научился считать суммарный рост всех учеников, находящихся в ряду на позициях от l до r. Но дети играют с ним злую шутку. В некоторый момент дети на позициях с l по r меняются местами. Учитель заметил, что у детей не очень богатая фантазия, поэтому они всегда "переворачивают" этот отрезок, т. е. l меняется с r, l + 1 меняется с r − 1 и так далее. Но учитель решил не ругать детей за их хулиганство, а все равно посчитать суммарный рост на всех запланированных отрезках.

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

В первой строке записано два числа n и m (1 ≤ n, m ≤ 200 000) — количество детей в ряду и количество событий, произошедших за все время. Во второй строке задано n натуральных чисел — рост каждого школьника в порядке следования в ряду. Рост детей не превосходит 2 ⋅ 10⁵. Далее в m строках задано описание событий: три числа q, l, r в каждой строке (0 ≤ q ≤ 1, 1 ≤ l ≤ r ≤ n). Число q показывает тип события: 0 показывает необходимость посчитать и вывести суммарный рост школьников на отрезке [l, r]; 1 показывает то, что дети на отрезке [l, r] "перевернули" свой отрезок. Все числа во входном файле целые.

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

Для каждого события типа 0 выведите единственное число на отдельной строке — ответ на этот запрос.

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

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

15
9
8
7
10

Задача C. Выборы заведующего кафедрой ≡

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача D. Фаброзавры-дизайнеры ≡

Условие

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

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

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

Первая строка входного файла содержит два числа N и M — длину дороги и количество запросов соответственно (1 ≤ N, M ≤ 10⁵). На второй строке содержатся N чисел, разделенных пробелами  — начальные высоты соответствующих частей дороги; высоты не превосходят 10⁴ по модулю. В следующих M строках содержатся запросы по одному на строке. Запрос + L~R~X означает, что высоту частей дороги от L-ой до R-ой (включительно) нужно изменить на X. При этом 1 ≤ L ≤ R ≤ N, а |X| ≤ 10⁴. Запрос ? L~R~X означает, что нужно проверить, есть ли между L-ым и R-ым участками (включая эти участки) участок, где дорога проходит точно на высоте X. Гарантируется, что 1 ≤ L ≤ R ≤ N, а |X| ≤ 10⁹.

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

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

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

10 5
0 1 1 3 3 3 2 0 0 1
? 3 5 2
+ 1 4 1
? 3 5 2
+ 7 10 2
? 9 10 3

NO
YES
YES

Задача E. Автоматизация склада ≡

Условие

Компания занимается автоматизацией склада. На складе хранятся n видов товаров, пронумерованных от 1 до n, каждый вид товара хранится в своём помещении. Товар вида i хранится в помещении с номером i.

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

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

В начале рабочего дня роботу поступил заказ на выдачу m товаров: a₁, a₂, …, a_m. Робот должен выдать товары именно в этом порядке. Для этого он последовательно выполняет следующие действия: открывает помещение, в котором лежит очередной товар, берет товар, закрывает помещение и выдаёт товар клиенту. После этого робот переходит к выдаче следующего товара.

Исходно электронные карты лежат в отсеке в следующем порядке, от верхней к нижней: b₁, b₂, …, b_n. Для каждого помещения в отсеке лежит ровно одна карта.

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

Требуется написать программу, которая по заданным целым числам n и m, последовательности выдаваемых товаров a₁, a₂, …, a_m и начальному положению карт в отсеке для хранения b₁, b₂, …, b_n определяет, какое минимальное количество действий придется совершить роботу, чтобы открыть все помещения в необходимом порядке. Для каждой вынутой карты необходимо также указать позицию, на которую её необходимо вернуть, чтобы добиться оптимального количества действий.

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

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

Вторая строка содержит m целых чисел a₁, a₂, …, a_m — типы товаров, которые необходимо выдать со склада, перечисленные в том порядке, в котором это необходимо сделать.

Третья строка содержит n различных целых чисел b₁, b₂, …, b_n — порядок, в котором карты исходно находятся в отсеке для их хранения, перечисленные от верхней к нижней.

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

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

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

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

Ограничения

1 ≤ n, m ≤ 3 ⋅ 10⁵

1 ≤ a_i ≤ n

1 ≤ b_i ≤ n

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

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

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

Во втором примере карты в отсеке робота перемещаются следующим образом:

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

1 1
1
1

1
1 

4 5
4 1 2 4 4
4 3 2 1

7
4 4 2 4 4 1 4 

2 2
1 2
2 1

3
2 2 2 

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

Условие

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

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

В первой строке входного файла заданы через пробел два целых числа 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

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

Условие

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

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

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

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

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

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

Ограничения

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

3 1
2 3

2

Задача C. Бюрократия ≡

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4

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

Условие

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

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

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

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

Ограничения

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

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

9

Задача E. Суперагент ≡

Условие

Женя Борин учится в школе юных суперагентов. На занятии по избавлению от слежки Борин получил такое теоретическое задание:

Зал аэропорта на плане имеет вид прямоугольника шириной W и высотой H метров. Пол разделён на клетки размером 1 × 1 метр. Клетка в северо-западном углу имеет координаты (1, 1).

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

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

Агент находится в точке с координатами (1, y_a) и желает попасть в точку с координатами (W, y_a), не подняв тревоги и затратив не более T секунд. Требуется написать программу, которая определит необходимую последовательность перемещений агента по известным координатам и перемещениям пассажиров.

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

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

Первая строка входного файла содержит числа W H T y_a N. Следующие N строк содержат значения x_i y_i p_i, где x_i, y_i — координаты i-го пассажира в начальный момент времени, p_i — строка из T символов, описывающая перемещения пассажиров в течении T секунд. Каждый символ равен "n", если пассажир перемещается на север, "s" — на юг, "w" — на запад, "e" — на восток, "z" — стоит на месте.

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

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