codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```