eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Заправочные станции

Заправочные станции

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

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

Каждый город имеет свой номер: 1, 2, 3 и так далее. Порядок нумерации указывает на порядок посещения городов, только начальная точка отправления не указана. Из города с наибольшим номером Вы должны ехать в город 1. Например, если имеются три города (пронумерованных 1, 2, 3), то у Вас имеется три варианта совершить путешествие:

Начать в 1, пойти в 2, затем в 3, и вернуться в 1.

Начать в 2, пойти в 3, затем в 1, и вернуться в 2.

Начать в 3, пойти в 1, затем в 2, и вернуться в 3.

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

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

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

Состоит из нескольких тестов. Каждый тест состоит из трех строк. Первая строка содержит количество городов. Вторая строка содержит количество топлива, доступного для дозаправки в городах в порядке номеров 1, 2, 3, и так далее. Третья строка содержит количество топлива, необходимого для достижения заправки в следующем городе в следующем порядке: от станции в городе 1 до станции в городе 2, от станции в городе 2 до станции в городе 3 и так далее; последнее число задает объем топлива, которое требуется чтобы проехать от города с последним номером до города номер 1. Все объемы топлива являются положительными целыми числами, заданы в имперских галлонах. Сумма поставок топлива не будет превышать 32-разрядных целых чисел. Существует как минимум два и не более 100000 городов. Последняя строка содержит ноль и не обрабатывается.

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

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

Пример

Входные данные #1
3
3 2 2
4 2 1
3
3 2 1
1 3 2
4
3 4 5 2
2 3 8 1
0
Выходные данные #1
Case 1: 2 3
Case 2: 1
Case 3: 4
Источник 2012 ACM North America - Rocky Mountain, Problem D