Задача №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 ≤ s ≤ 1 000. Решение оценивается в 40 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 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