3. «Цирковое шоу» (15 баллов)
В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.
Шоу состоит из n небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление i начинается через si минут от начала шоу и продолжается ti минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).
Публика любит и представления со львами, и представления с тиграми. Дрессировщики просят вас помочь им распределить представления между львами и тиграми так, чтобы минимум из числа представлений с львами и числа представлений с тиграми был как можно больше.
Ограничения:
.
Ввод из файла show.in. Первая строка входного файла содержит число n. Следующие n строк содержат пары чисел si, ti.
Вывод в файл show.out. Выведите в выходной файл n чисел. Число номер i должно быть равно 1, если в i-ом представлении участвуют львы, или 2, если участвуют тигры, или 0, если не участвуют ни те ни другие.
Пример
Ввод
5
8 3
0 7
4 5
1 2
11 3
Вывод
1 0 1 2 2
4. «Красивая таблица» (10 баллов)
Олег — известный поклонник соревнований по программированию. Он знает всех участников всех соревнований за последние десять лет и может про любого участника сказать, сколько задач решила команда с его участием на любом соревновании. И еще Олег очень любит теорию чисел.
В таблице результатов соревнования по программированию команды упорядочены по убыванию количества решенных задач. Олег называет таблицу результатов красивой, если для всех команд количество решенных ими задач равно нулю или является делителем количества задач на соревновании. Когда какая-нибудь команда сдает задачу, количество сданных задач у нее увеличивается на один. Никакая команда не может сдать две или более задач одновременно, также две команды не могут одновременно сдать задачу.
Глядя на красивую таблицу результатов, Олег заинтересовался: а сколько еще задач смогут суммарно сдать команды так, чтобы после каждой сданной задачи таблица результатов оставалась красивой? Помогите ему выяснить это.
Ограничения:
.
Ввод из файла standing.in. Первая строка входного файла содержит два целых числа: n и m — количество команд и количество задач на соревновании, соответственно. Вторая строка содержит n целых чисел, упорядоченных по невозрастанию: для каждой команды задано, сколько задач она решила. Гарантируется, что все отличные от нуля числа являются делителями числа m.
Вывод в файл standing.out. Выведите в выходной файл одно число: максимальное количество задач, которое суммарно могут еще сдать команды так, чтобы после каждой сданной задачи таблица результатов оставалась красивой..
Пример
Ввод
7 12
12 6 4 3 3 1 0
Вывод
9