1433E.md (1737B)
1 Source: https://codeforces.com/problemset/problem/1433/E 2 3 E. Two Round Dances 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 One day, $n$ people ($n$ is an even number) met on a plaza and made two round dances, each round dance consists of exactly $\frac{n}{2}$ people. Your task is to find the number of ways $n$ people can make two round dances if each round dance consists of exactly $\frac{n}{2}$ people. Each person should belong to exactly one of these two round dances. 22 23 Round dance is a dance circle consisting of $1$ or more people. Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances $[1, 3, 4, 2]$, $[4, 2, 1, 3]$ and $[2, 1, 3, 4]$ are indistinguishable. 24 25 For example, if $n=2$ then the number of ways is $1$: one round dance consists of the first person and the second one of the second person. 26 27 For example, if $n=4$ then the number of ways is $3$. Possible options: 28 29 * one round dance — $[1,2]$, another — $[3,4]$; 30 * one round dance — $[2,4]$, another — $[3,1]$; 31 * one round dance — $[4,1]$, another — $[3,2]$. 32 33 Your task is to find the number of ways $n$ people can make two round dances if each round dance consists of exactly $\frac{n}{2}$ people. 34 35 Input 36 37 The input contains one integer $n$ ($2 \le n \le 20$), $n$ is an even number. 38 39 Output 40 41 Print one integer — the number of ways to make two round dances. It is guaranteed that the answer fits in the $64$-bit integer data type. 42 43 Examples 44 45 Input 46 47 ``` 48 2 49 ``` 50 51 Output 52 53 ``` 54 1 55 ``` 56 57 Input 58 59 ``` 60 4 61 ``` 62 63 Output 64 65 ``` 66 3 67 ``` 68 69 Input 70 71 ``` 72 8 73 ``` 74 75 Output 76 77 ``` 78 1260 79 ``` 80 81 Input 82 83 ``` 84 20 85 ``` 86 87 Output 88 89 ``` 90 12164510040883200 91 ```