|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1723. Trees
|
| View Problem Statistics | Submit | Problem added debug |
|
Как известно, связный граф без циклов называется деревом. Однажды на лекции по дискретной математики Вася узнал, что на N вершинах с номерами 1, 2, ..., N можно построить ровно NN - 2 различных деревьев (формула Кэли). Два дерева считаются различными, если существуют две такие вершины с номерами u и v, что в одном дереве есть ребро между u и v, а в другом — нет. В качестве домашнего задания Васе предложили определить, сколько различных деревьев можно построить на вершинах 1, 2, ..., N при дополнительном условии, что каждое ребро может соединять только вершину с чётным номером с вершиной с нечётным номером. Васе это задание показалось непростым. А вам? Входные данные В единственной строке записано одно натуральное число N (1 ≤ N ≤ 20). Выходные данные Одно целое число – количество деревьев Примеры Входные данные 3 Выходные данные 1 Входные данные 4 Выходные данные 4 Примечание Все возможные деревья для второго примера показаны на рисунке: 
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Vologda Students Contests / | XX Interuni Olympiad - 2017 / |
| 1722. C - Contest | 1723. | 1724. E - Subtracting of Squares | 1725. F - Polynom's Factorization | 1726. G - Botanic Garden |
| time generating 0.078 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |