#915

Самый дешевый путь

Темы: [Динамическое программирование: один параметр]

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.

Входные данные

В первой строке входного файла вводится одно натуральное число \(N\le100\) — количество ступенек.
В следующей строке вводятся \(N\) натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выходные данные

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Примеры

Входные данные

3
1 3 1

Выходные данные

#941

Не в билетах счастье, а в их количестве

Темы: [Динамическое программирование]

Люди, покупающие какие-либо билеты, часто пытаются понять, на сколько счастливый билет им попался. При этом определения счастья бывают различные. В общественном транспорте Кирова для нумерации билетов используются числа от 1 до n. Витя считает билет счастливым, если его номер делится на сумму его цифр. Помогите Вите определить количество счастливых билетов.

Входные данные

На вход подается число n (1 ≤ n ≤ 10¹²).

Выходные данные

Выведите количество счастливых билетов в диапазоне от 1 до n.

Примеры

Входные данные

Выходные данные

#943

Треугольник Паскаля

Темы: [Рекуррентные последовательности]

Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнееиз этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.

Входные данные

Вводится одно число N (0<=N<=30).

Выходные данные

Вывести N строк треугольника Паскаля (числа выводятся через пробел).

Примеры

Входные данные

Выходные данные

#944

Cамый дешевый путь

Темы: [Динамическое программирование на таблицах]

В каждой клетке прямоугольной таблицы \(N\times M\) записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Входные данные

Вводятся два числа \(N\) и \(M\) — размеры таблицы (\(1\le N\le20\), \(1\le M\le20\)). Затем идет \(N\) строк по \(M\) чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные

Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Примеры

Входные данные

5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1

Выходные данные

#945

Шашку - в дамки

Темы: [Динамическое программирование на таблицах]

Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача O ]

На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Входные данные

Вводятся два числа от 1 до 8: номер столбца (считая слева) и номер строки (считая снизу), где изначально стоит шашка.

Выходные данные

Вывести одно число - количество путей в дамки.

Примеры

Входные данные

3 7

Выходные данные

Входные данные

1 8

Выходные данные

Входные данные

3 6

Выходные данные