#3677

Dance Party

Темы: [Разные комбинаторные структуры] [Вещественные числа]

#3678

Сушка

Темы: [Жадный алгоритм]

Тетя Люба только что постирала все белье, и теперь перед ней стоит непростая задача: как его высушить, чтобы ни одна вещь не успела испортиться. Сразу после стирки \(i\)-я постиранная вещь имеет влажность \(w_i\). Если она сушится на веревке, то за минуту ее влажность уменьшается на \(1\), а если на батарее— то на \(r\) (если влажность была меньше \(r\), то она становится равной \(0\)). Причем веревок у тети Любы много (хватает для одновременной сушки всех вещей), а батарея только одна, причем такая маленькая, что на ней нельзя сушить две вещи одновременно. \(i\)-я вещь испортится, если не высохнет за время \(d_i\). Помогите тете Любе составить план, когда какую вещь повесить на батарею.

Входные данные

Первая строка входного файла содержит целые числа \(n\) (\(1 \leq n \leq 10^5\)) (количество мокрых вещей) и \(r\) (\(1 \leq r \leq 10^9\)). Следующие \(n\) строк содержат описания постиранных вещей — пары чисел \(w_i\) и \(d_i\) (\(1 \leq w_i, d_i \leq 10^9\)).

Выходные данные

Выведите план сушки в виде пар целых чисел \(t_i\) и \(k_i\), где \(t_i\) — измеренное в минутах время от начала сушки, а \(k_i\) — номер вещи, которую нужно повесить на батарею в этот момент. Выводите пары в порядке увеличения \(t_i\). Пар не должно быть больше \(100\,000\). Не выводите числа больше \(10^9\).

Если высушить все вещи невозможно, выведите слово Impossible.

Примеры

Входные данные

Выходные данные

0 1
500 3

Входные данные

Выходные данные

Impossible

#3679

Tanks a lot

Темы: [Стек]

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

Входные данные

Входной файл содержит нескольно тестовых примеров (не более 50). Каждый тестовый пример начинается со строки, содержащей два положительных числа \(c\) и \(s\) (\(c \leq 100\,000\)): длину окружности (в километрах) и количество заправочных станций. Далее следуют \(s\) пар целых чисел \(t\) и \(m\). В каждой паре \(t\) - это целое число от \(0\) до \(c - 1\), означающее позицию этой АЗС, измеренную по часовой стрелке от некоторой произвольной фиксированной точки окружности, а \(m\) - это количество километров, которое можно проехать, используя весь бензин с этой станции. Все позиции различны. За последним тестовым примером следует пара нулей.

Выходные данные

Для каждого тестового примера выведите его номер (в формате, показанном в примере), а затем список пар значений в виде \(i\) \(d\), где \(i\) - это позиция заправочной станции, а \(d\) - это либо C либо CC, либо CCC, означающих, что, стартовав с пустым бензобаком, можно проехать по марштуту из позиции \(i\) по часовой стрелке (C) против часовой стрелки (CC) или в любом направлении (CCC) и вернуться в позицию \(i\). Станции нужно выводить в порядке возрастания позиции.

Подзадача 1

1 ≤ s ≤ 1 000. Решение оценивается в 40 баллов.

Подзадача 2

Дополнительные ограничения отсутствуют. Решение оценивается в 60 баллов.

Примеры

Входные данные

10 4
2 3 4 3 6 1 9 3
5 5
0 1 4 1 2 1 3 1 1 1
0 0

Выходные данные

Case 1: 2 C 4 CC 9 C
Case 2: 0 CCC 1 CCC 2 CCC 3 CCC 4 CCC

#3683

Алгоритм Евклида

Темы: [НОД и алгоритм Евклида]

Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел \(a\) и \(b\) называется наибольшее натуральное число \(x\), такое, что и число \(a\), и число \(b\) делится на него без остатка. Алгоритм Евклида заключается в следующем:

Пусть \(a\), \(b\) – числа, НОД которых надо найти.
Если \(b = 0\), то число \(a\) – искомый НОД.
Если \(b > a\), то необходимо поменять местами числа \(a\) и \(b\).
Присвоить числу \(a\) значение \(a - b\).
Вернуться к шагу 2.

Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа \(a\), \(b\), \(c\) и \(d\). Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (\(a\), \(b\)) такой момент, когда перед исполнением шага 2 число \(a\) будет равно \(c\), а число \(b\) будет равно \(d\).

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

Входные данные

Первая строка входных данных содержит количество наборов входных данных \(K~(1 \le K \le 100)\). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: \(a\), \(b~(1 \le a, b \le 10^{18})\). Вторая строка – два целых числа: \(c, d~(1 \le c, d \le 10^{18})\).

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

Выходные данные

Для каждого набора входных данных выведите слово "YES", если в процессе применения алгоритма Евклида к паре чисел (\(a\), \(b\)) в какой-то момент получается пара (\(c\), \(d\)). В противном случае выведите слово "NO".

Система оценки

Тесты к данной задаче состоят из двух групп:

\(1 \le K \le 5\), \(1 \le a, b, c, d \le 10^6\). Эта группа оценивается в 60 баллов.
Дополнительных ограничений нет. Эта группа оценивается в 40 баллов.

#3701

Посадка в поезд

Темы: [Дерево отрезков, RSQ, RMQ] [Декартово дерево]

Цифровой поезд нового поколения состоит из вагонов, содержащих по \(N\) мест для пассажиров. Все места расположены вдоль вагона и пронумерованы от \(1\) до \(N\). Вход в вагон расположен левее места \(1\), а места \(1, 2, \ldots, N\) расположены правее от входа в соответствующем порядке. \(N\) пассажиров готовятся сесть в поезд. Каждый заходящий в вагон характеризуется номером места \(A_i\) и своей массой \(B_i\). Когда пассажир идет по вагону от входа до своего места, некоторые пассажиры, которые сели ранее, мешают ему пройти. Пассажир испытывает неудобство, каждый раз проходя мимо человека массы большей, чем у него самого. Суммарным неудобством пассажира при посадке называется количество раз, когда он испытывал неудобство при движении к своему месту от входа в вагон. Ваша задача — по заданному порядку посадки пассажиров найти суммарное неудобство каждого.

Входные данные

Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается с целого числа \(N\; (1 \leq N \leq 100\,000)\) — количества мест (пассажиров). Далее набор входных данных содержит пары целых чисел \(A_i, B_i\; (1 \leq A_i \leq N, 1 \leq B_i \leq 10^9)\). Все числа \(A_i\) и \(B_i\) различны между собой. То есть номера мест пассажиров образуют перестановку. Пассажиры садятся в поезд именно в том порядке, в котором они заданы во входном файле. Количество наборов входных данных не превосходит \(5\).

Выходные данные

Выведите ответ на каждый набор входных данных. Каждый ответ должен состоять из последовательности \(N\) целых чисел \(P_1, P_2, \ldots, P_N\), где \(P_i\) — суммарное неудобство \(i\)-го пассажира.

Пример

Ввод

Вывод

0 0 2
0 0