11308. ICPC строки

Определим ICPC-строку как строку, состоящую из букв ICPC, такую что любые 4 последовательные буквы содержат две буквы C, одну букву I и одну букву P.

Для заданного n ≥ 4 найдите количество различных ICPC-строк длины n.

Вход. Содержит одно целое число n (4 ≤ n ≤ 1000) – длину строки.

Выход. Выведите одно целое число – количество ICPC-строк длины n.

Пример входа	Пример выхода
5	12

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Число анаграмм слова ICPC равно 4! / (2! * 2!) = 12.

Пятый символ ICPC-строки определяется однозначно первыми четырьмя. Со второго по пятый символ (4 последовательные буквы) должны стоять две буквы C, одна буква I и одна буква P. Следовательно пятый символ должен совпадать с первым. По этой же причине 6-ой символ должен совпадать со вторым и так далее.

Таким образом, ICPC-строка однозначно определяется первыми четырьмя символами. Поэтому количество ICPC-строк равно числу анаграмм слова ICPC независимо от длины слова n.

Пример

Рассмотрим примеры ICPC-строк:

· ICPCICPCICPCICPCICPC…

· CCPICCPICCPICCPICCPI…

· PCICPCICPCICPCICPCIC…

Реализация алгоритма

Для решения задачи достаточно вывести одно число 12.

printf("12\n");