Динамічне програмування

Досить часто на олімпіадах зустрічаються завдання, що провокують до застосування алгоритми перебору. Але простий підрахунок числа варіантів переконує в неефективності такого підходу. Для вирішення таких завдань використовується метод динамічного програмування. Суть його полягає в тому, що для відшукання рішення поставленого завдання вирішується схожа (або схожі), але більш проста. При цьому здійснюється перехід до ще більш простим і так далі, поки не доходять до тривіальною.

З попереднього міркування видно, що рішення можна оформити рекурсивно. Але просте застосування цього прийому дуже легко може призвести до переповнення стека. Необхідно подбати про оптимізацію рекурсивних проходів і не обчислювати одне й те саме значення кілька разів, зробити так зване відсікання. Можна взагалі відмовитися від рекурсії і вирішувати завдання "навпаки" - перш "вирішити" тривіальні випадки, а потім переходити до все більш складним. У авторських рішення подібних завдань майже завжди зустрічається другий шлях (він трохи швидше), але в цьому занятті розглянемо обидва - перший набагато доступніше для розуміння.

Для вирішення таких завдань існує спеціальна теорія, велика заслуга в її створенні належить Р. Беллману. У загальному вигляді вона досить складна, тому тут не розглядається. У той же час конкретні завдання, розглянуті нижче, цілком можуть сформувати (хоча б на інтуїтивному рівні) ідеї, що лежать в основі рішення задач даного класу.

Перші два завдання, строго кажучи, не можна віднести до зазначеного класу, але прийоми, використані при їх вирішенні, дуже схожі з такими у завдань, що розглядаються на цьому занятті. Інші завдання свого часу зустрічалися на різних олімпіадах (а деякі з тих пір стали "фольклорними") і розташовані (на думку автора публікації) у порядку зростання складності. Для простоти будемо вважати, що в більшості завданнях вихідні дані такі, що результат поміститься в тип LongInt. Справедливості заради відзначимо, що таке обмеження існує не завжди, і в останніх двох завданнях доводиться або використовувати тип Double, або додатково реалізовувати "довгу арифметику".

Числа Фібоначчі

Обчислити N-е число в послідовності Фібоначчі, - 1, 1, 2, 3, 5, 8, ... - В якій перші два члени дорівнюють одиниці, а всі інші представляють собою суму двох попередніх.

Формат вхідних даних

Одне число 0