Задача 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