Тренировка по теме «Динамическое программирование»
Соревнование завершилось 22.10.18 в 00:00
A. Глупый Шахматный Король
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ
Имеется шахматная доска размером N × N клеток. В нижней левой клетке стоит редкая шахматная фигура — «Глупый король», которая может перемещаться только на соседнюю справа или сверху клетку.
Очевидно, что «Глупый король» имеет конечное количество способов добраться из левой нижней клетки доски в правую верхнюю, не поднимаясь выше побочной диагонали. Ваша задача — посчитать это количество для заданного значения N.
Единственная строка входных данных содержит целое число N (1 ≤ N ≤ 20).
Единственная строка выходных данных должна содержать единственное число — количество способов «Глупому королю» добраться из левой нижней клетки доски в правую верхнюю, не поднимаясь выше побочной диагонали.
Стандартный ввод | Стандартный вывод |
---|---|
1 | 1 |
3 | 2 |