Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 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

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

Условие

Доказать, что разносторонний треугольник нельзя разрезать на два равных треугольника.

Решение

Предположим, что отрезок CD разрезает разносторонний треугольник ABC на два равных треугольника ACD и BCD. Эти треугольники имеют, в частности, равные площади, поэтому AD = BD. Кроме того, сторона CD общая. Следовательно, оставшиеся стороны равны, т.е. AC = BC. Приходим к противоречию.

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