Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

7	8	9
4	5	6
1	2	3
	0

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные
Выведите в выходной файл искомое количество телефонных номеров.

Пример входного файла
2

Пример выходного файла
16

   Решение

Темы:    [ Системы точек ] [ Подсчет двумя способами ] [ Разные задачи на разрезания ]

Сложность: 3 Классы: 8,9,10

Прислать комментарий

Условие

Внутри квадрата отмечено 100 точек. Квадрат разбит на треугольники таким образом, что вершинами треугольников являются только отмеченные 100 точек и вершины квадрата, причём для каждого треугольника разбиения каждая отмеченная точка либо лежит вне этого треугольника, либо является его вершиной (разбиения такого типа называются триангуляциями). Найдите число треугольников разбиения.

Подсказка

Подсчитайте сумму углов всех треугольников.

Решение

Сумма углов треугольников с вершиной в некоторой вершине квадрата равна 90°, каждая из отмеченных 100 точек даёт вклад, равный 360°. Поскольку других вершин треугольников нет, то сумма углов всех треугольников разбиения равна  100·360° + 4·90° = 202·180°.  Поскольку сумма углов треугольника равна 180°, то количество треугольников равно 202.

Ответ

202 треугольника.

Источники и прецеденты использования