С++ олимпиадная задача
Старый пират Пью спрятал свое золото, но для надежности не в одном месте, а частями в нескольких тайниках. Но чтобы не забыть места хранения клада он составил карту. Карта представляет собой упорядоченную последовательность тайников в каждом из которых записано целое число. Положительное число, записанное в тайнике, обозначает номер тайника, к которому следует перейти; отрицательное число - часть золотого клада, стоимость которого равна абсолютному значению содержимого этого тайника. Выбрав золото из текущего тайника, искатель переходит к следующему тайнику по списку. Если искатель клада добрался до пустого тайника или до последнего в списке, то это означает, что все доступное золото собрано и можно уносить ноги, пока цел (за золотом пирата Пью охотятся и другие искатели). Но если искатель вскроет тайник, содержимое которого равно 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
Какая-то рекурсия мыслей получается...
В то же время эта задача в архиве задач идёт сразу после задач на индексацию, сбивает с толку, может лучше создать кучу массивов, или как-либо пересортировать исходный?
Как Вы считаете, я на верном пути, или упускаю что-то очевидное?
Вроде простая задача (или я что-то неправильно понял), бесконечных циклов не будет, т. к. тайник после посещения обнуляется. Можно и рекурсией, но зачем?
Псевдокод:
sum = 0;
i = 0;
while (i < n && a[i] != 0 && a[i] != 666)
{
if (a[i] > 0)
{
temp = a[i];
a[i] = 0;
i = temp - 1;
}
else
{
sum -= a[i];
a[i] = 0;
i++;
}
}
if (i >= n || a[i] == 0)
print(sum);
else
print("RIP");
-
21:33
Виртуальный выделенный сервер (VDS) становится отличным выбором
-
22:26
-
22:40
-
08:34
-
15:01
-
17:01
-
11:24
-
10:16
-
17:54
- Почему SERVER_ADDR имеет не тот IP 47689 visits
- Как заменить $_SERVER[REMOTE_ADDR] на IP клиента в PHP за двумя Nginx? 30538 visits
- Хочу вывести несколько строк из массива в один div, выводит только много undefined; подскажите, что делать? 23716 visits
- Как через css изменить цвет png изображения? 10368 visits
- Blob video url download 9977 visits
- Php curl запрос через прокси с авторизацией 9235 visits
- Работа с captcha vk api 8112 visits
![C++ циклический сдвиг влево [закрыт]](https://hostciti.net/images/nophoto.png "C++ циклический сдвиг влево [закрыт]")
© "hostciti.net" 19.1.2025 | 13:29