Динамічне
програмування
Досить часто
на олімпіадах зустрічаються завдання, що провокують до застосування алгоритми
перебору. Але простий підрахунок числа варіантів переконує в неефективності такого
підходу. Для вирішення таких завдань використовується метод динамічного
програмування. Суть його полягає в тому, що для відшукання рішення
поставленого завдання вирішується схожа (або схожі), але більш проста. При цьому
здійснюється перехід до ще більш простим і так далі, поки не доходять до
тривіальною.
З попереднього
міркування видно, що рішення можна оформити рекурсивно. Але просте застосування
цього прийому дуже легко може призвести до переповнення стека. Необхідно
подбати про оптимізацію рекурсивних проходів і не обчислювати одне й те саме
значення кілька разів, зробити так зване відсікання. Можна взагалі
відмовитися від рекурсії і вирішувати завдання "навпаки" - перш
"вирішити" тривіальні випадки, а потім переходити до все більш складним.
У авторських рішення подібних завдань майже завжди зустрічається другий шлях (він
трохи швидше), але в цьому занятті розглянемо обидва - перший набагато доступніше
для розуміння.
Для вирішення
таких завдань існує спеціальна теорія, велика заслуга в її створенні
належить Р. Беллману. У загальному вигляді вона досить складна, тому тут не
розглядається. У той же час конкретні завдання, розглянуті нижче, цілком
можуть сформувати (хоча б на інтуїтивному рівні) ідеї, що лежать в основі
рішення задач даного класу.
Перші два
завдання, строго кажучи, не можна віднести до зазначеного класу, але прийоми,
використані при їх вирішенні, дуже схожі з такими у завдань, що розглядаються
на цьому занятті. Інші завдання свого часу зустрічалися на різних
олімпіадах (а деякі з тих пір стали "фольклорними") і розташовані
(на думку автора публікації) у порядку зростання складності. Для простоти
будемо вважати, що в більшості завданнях вихідні дані такі, що результат
поміститься в тип LongInt. Справедливості заради відзначимо, що таке обмеження
існує не завжди, і в останніх двох завданнях доводиться або використовувати
тип Double, або додатково реалізовувати "довгу арифметику".
Числа Фібоначчі
Обчислити N-е
число в послідовності Фібоначчі, - 1, 1, 2, 3, 5, 8, ... - В якій
перші два члени дорівнюють одиниці, а всі інші представляють собою суму двох
попередніх.
Формат вхідних
даних
Одне число
0
Формат вихідних
даних
Одне число --
N-й член послідовності.
М'ячик на
драбинці
На вершині
драбинки, яка містить N сходинок, знаходиться м'ячик, який починає стрибати по
ним вниз, до основи. М'ячик може стрибнути на наступну сходинку, на
сходинку через одну або через 2. (Тобто, якщо м'ячик лежить на 8-й сходинці,
то він може переміститися на 5-у, 6-у або 7-у.) Визначити число
всіляких "маршрутів" м'ячика з вершини на землю.
Формат вхідних
даних
Одне число
0
Формат вихідних
даних
Одне число --
кількість маршрутів.
Черепашка
На квадратної
дошці розставлені цілі невід'ємні числа. Черепашка, що знаходиться в лівому
верхньому куті, мріє потрапити в правий нижній. При цьому вона може переповзати
тільки в клітку праворуч або знизу і хоче, щоб сума всіх чисел, які опинилися у
неї на шляху, була б максимальною. Визначити цю суму.
Формат вхідних
даних
Перший рядок --
N - розмір дошки.
Далі йде N
рядків, кожен з яких містить N цілих чисел, що представляють дошку.
Формат вихідних
даних
Одне число --
максимальна сума.
Робот
В
дослідної лабораторії фірми Robots & Co розробили нову модель робота.
Головною особливістю даної моделі робота є те, що він працює за
заздалегідь заданою програмою, в якій можуть бути присутні команди: зробити крок
на Південь, на Північ, на Схід або на Захід. Робот виконує програму строго
послідовно і, дійшовши до кінця програми, зупиняється. Фахівці з
Robots & Co зацікавилися питанням, скільки існує різних програм,
складаються з K інструкцій, таких, що робот, вийшовши з початку координат, прийде
в точку з координатами (X, Y). Осі координат розташовуються паралельно сторонам
світла, і одиниця виміру, відповідає одному кроку робота. Напишіть
програму, яка дає відповідь на це питання.
Формат вхідних
даних
У вхідному
файл знаходяться три числа K, X і Y (0 <= K <= 16, | X |, | Y | <= 16),
розділені пропусками.
Формат вихідних
даних
У вихідний файл
ваша програма повинна помістити одне число - кількість програм для робота.
Вибухонебезпечність
При переробці
радіоактивних матеріалів утворюються відходи двох видів - особливо небезпечні (тип A) і
безпечні (тип B). Для їхнього збереження використовуються однакові контейнери. Після
приміщення відходів у контейнери, останні укладаються вертикальної стопкою.
Стопка вважається вибухонебезпечною, якщо в ній поспіль йде більше двох контейнерів
типу A. Для заданої кількості контейнерів N визначити число безпечних
стопок.
Формат вхідних
даних
Одне число
0
Формат вихідних
даних
Одне число --
кількість безпечних варіантів формування стопки.
К-ічние числа
Потрібно
обчислити кількість N-значних чисел у системі числення з основою K, таких
що їх запис не має двох поспіль нулів.
Обмеження:
2 <= K <= 10, N + K <= 18.
Формат вхідних
даних
Числа N и K в
десяткового запису, розділені пробілом або переказом рядка.
Формат вихідних
даних
шукалося число в
десяткового запису.
Подпаліндром
Паліндроми
називається рядок, який однаково читається як зліва направо, так і справа
наліво. Подпаліндромом цього рядка називається послідовність символів з
цього рядка, не обов'язково йдуть підряд, що є паліндромом. Наприклад,
HELOLEH є подпаліндромом рядка HTEOLFEOLEH. Напишіть програму,
що знаходить у цьому рядку подпаліндром максимальної довжини.
Формат вхідних
даних
Рядок довжиною
не більше 100 символів, що складається з великих літер латинського алфавіту.
Формат вихідних
даних
У першому рядку
вивести довжину максимального подпаліндрома, а у другому рядку сам максимальний
подпаліндром. Якщо таких подпаліндромов декілька, то вивести будь-який з них.
Паровозик
N локомотивів,
що мають номери від 1 до N і встановлених на залізничну колію, починають
рухатися в один бік, причому локомотив номер k спочатку рухається зі
швидкістю k км/ч. Якщо локомотив, який рухається з більшою швидкістю, сном
повільніший локомотив, далі вони рухаються один за одним зі швидкістю
що йде попереду локомотива. Очевидно, через деякий час після початку
руху локомотиви розіб'ються на кілька груп, що рухаються з різною
швидкістю.
Написати
програму, яка визначить, скільки початкових розстановок s з N! Можливих дадуть
в результаті p груп рухомих локомотивів.
Формат вхідних
даних
Два числа - 0
Формат вихідних
даних
Одне число - s.
Плитки
У Петі є
необмежений набір червоних, синіх і зелених плиток розміром 1 * 1. Він
вибирає рівно Nпліток і викладає їх у смужку. Наприклад, при N = 10 вона може
виглядати наступним чином:
К
К
К
С
З
К
К
З
К
С
(буквою К
позначена червона плитка, С - синя, З - зелена).
Після цього
Петя заповнює наступну таблицю:
Червоний
Синий
Зелений
Червоний
Y
Y
Y
Синий
Y
N
Y
Зелений
Y
Y
N
У клітці на
перетині рядка, що відповідає цвіту А, і стовпця, що відповідає кольору Б, він
записує "Y", якщо в його смужці знайдеться місце, де поруч лежать
плитки квітів А і Б і "N" в іншому випадку. Вважається, що плитки
лежать поруч, якщо у них є спільна сторона. (Очевидно, що таблиця симетрична
щодо головної діагоналі - якщо плитки квітів А і Б лежали поруч, то
поруч лежали і плитки квітів Б і А.) Назвемо таку таблицю діаграмою суміжності
даної смужки.
Так, дана
таблиця являє собою діаграму суміжності наведеної вище смужки.
Петя хоче
дізнатися, скільки різних смужок має певну діаграму суміжності.
Допоможіть йому.
(Зауважте, що
смужки, що є відображенням один одного, але не збігаються, вважаються
різними. Так, смужка
С
К
З
К
К
З
С
К
К
К
не збігається з
смужкою, наведеної на початку умови.)
Формат вхідних
даних
Перший рядок
вхідного файлу містить число N (1 <= N <= 100). Наступні три рядки
вхідного файлу, що містять по три символи з набору ( "Y",
"N"), відповідають трьох рядків діаграми суміжності. Інших
символів, включаючи пробіли, у вхідному файлі не міститься. Вхідні дані
коректні, тобто діаграма суміжності симетрична.
Формат вихідних
даних
Виведіть в
вихідний файл кількість смужок довжини N, мають наведену у вхідному файлі
діаграму суміжності.
Список
літератури
Е.В. Бризгалов.
Динамічне програмування.
Для підготовки
даної роботи були використані матеріали з сайту http://www.comp-science.narod.ru/
