Разбор задач школьного этапа олимпиады по информатике 2018 года. Задача E

Дата публикации: Oct 21, 2018 4:53:42 PM

Задача E. Строки Фибоначчи

Ограничения в задаче таковы, что решить ее моделированием невозможно.

Строка S может находиться в строке F(N) либо в начале строки (в F(N-1)), либо в конце строки (в F(N-2)), либо в месте склейки этих строк, когда начало данной строки является концом N-1 строки, а конец - началом N-2 строки. Если хранить число вхождений во все предыдущие строки Фибоначчи, посчитать первый и второй случай легко.

Посчитать число вхождений в места склейки можно, если хранить в отдельных массивах строк начала и концы строк Фибоначчи. Для подсчета количества вхождений третьего вида склеиваем конец N-1 строки и начало N-2 строки и осуществляем проверку непосредственно. (скачать, .pas)