Задача в том, чтобы быстро находить n-тый член последовательности Голомба.
Но вариант находить последовательность полностью с помощью ДП и брать dp[n]
не подходит, так как затратит больше положенных 255 Мб
, т. к. n <= 2e9
.
А рекурсивное решение неподходит, т. к. рекурсия выходит слишком глубокой. Возможное решение проблемы - разворот рекурсии.
Как это можно реализовать?
P.s.: Так же на нахождение элемента последовательности даётся порядка одной секунды на не самом сильном железе.
findGolomb(int n) {
if(n == 1) return 1;
return 1 + findGolomb(n -
findGolomb(findGolomb(n - 1)));
}
2е9
– Kir_Antipov 20 янв в 10:50