Старый пират Пью спрятал свое золото, но для надежности не в одном месте, а частями в нескольких тайниках. Но чтобы не забыть места хранения клада он составил карту. Карта представляет собой упорядоченную последовательность тайников в каждом из которых записано целое число. Положительное число, записанное в тайнике, обозначает номер тайника, к которому следует перейти; отрицательное число - часть золотого клада, стоимость которого равна абсолютному значению содержимого этого тайника. Выбрав золото из текущего тайника, искатель переходит к следующему тайнику по списку. Если искатель клада добрался до пустого тайника или до последнего в списке, то это означает, что все доступное золото собрано и можно уносить ноги, пока цел (за золотом пирата Пью охотятся и другие искатели). Но если искатель вскроет тайник, содержимое которого равно 666, то сработает капкан и ... поминай, как звали:(
Определить общую стоимость клада. Если искатель клада попал в капкан, то вывести "RIP". Искатель начинает поиск клада с первого тайника. После вскрытия тайник обнуляется.
Во входном потоке в первой строке задано натуральное число N (N < 1000). Во второй строке целые числа, перечисленные через пробел - карта тайников. Значение, записанное в тайнике задано в диапазоне -32000 <= Ai <= N.
Например,
8 5 4 -10 666 3 8 6 7
В выходной поток вывести единственное целое число или слово "RIP". Например,
RIP
Хочу сам прийти к решению, но торможу на одном месте( Понятно, что нужно обращаться к рекурсивной функции из цикла, которая будет возвращать следующую подсказку до тех пор, пока не возвратит либо 666, либо отрицательное значение.
В целом представляю решение так:
- инициализация sum=0
- создаём массив и заполняем его
- проходим в цикле значения массива
- вызываем рекурсивную функцию, передаём в неё массив, текущий элемент (значение)
- функция вызывает сама себя, если она возвращает положительное значение !=666
- если 666 выходим из функции, цикла, пишем RIP, break
- если вернёт <0 тогда sum+=abs(), continue
- вызываем рекурсивную функцию, передаём в неё массив, текущий элемент (значение)
- когда цикл завершён выводим сумму
Столкнулся с тремя явными проблемами:
- Возможна бесконечная рекурсия, нужно как-то из неё выйти
- Нужно как-то пометить, что клад мы забрали, помечаем нулём?
- Если функция вызывает сама себя, то как она может вернуться к циклу???
Получается, что считать сумму нужно в самой функции, но тогда смысл цикла заключается в том, чтобы переходить к другому элементу, если столкнулись с нулём и контролировать 666
Какая-то рекурсия мыслей получается...
В то же время эта задача в архиве задач идёт сразу после задач на индексацию, сбивает с толку, может лучше создать кучу массивов, или как-либо пересортировать исходный?
Как Вы считаете, я на верном пути, или упускаю что-то очевидное?