== include(page="template/taskheader" task_id="petrecere") ==
Poveste şi cerinţă...
Se organizează o petrecere la care participă $N$ băieţi (numerotaţi de la $1$ la $N$) şi $N$ fete (numerotate de la $1$ la $N$). S-a decis ca petrecerea să dureze mai multe minute. În fiecare minut fetele şi băieţii formează o configuraţie de dans, adică $N$ perechi, după una din următoarele reguli:
* băiatul $i$ dansează cu fata $i$;
* băiatul $i$ dansează cu fata $j$ şi atunci obligatoriu băiatul $j$ dansează cu fata $i$.
Prin perechea $(i, j)$ s-a notat faptul că băiatul $i$ dansează cu fata $j$. Două configuraţii sunt distincte dacă ele diferă prin cel puţin o pereche. Pentru $N = 7$, două configuraţii de dans posibile sunt:
$(1, 1) (2, 2) (3, 7) (4, 5) (5, 4) (6, 6) (7, 3)$
$(1, 1) (2, 2) (3, 3) (4, 5) (5, 4) (6, 6) (7, 7)$
h2. Cerinţă
Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.
h2. Date de intrare
Fişierul de intrare $petrecere.in$ ...
Fişierul de intrare $petrecere.in$ conţine pe prima linie un singur număr natural $N$.
h2. Date de ieşire
În fişierul de ieşire $petrecere.out$ ...
Fişierul de ieşire $petrecere.out$ va conţine o singură linie pe care va fi scris un singur număr natural reprezentând durata în minute a petrecerii.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 2000$
* Răspunsul este un număr natural de maximum $3000$ de cifre.
* Pentru $20%$ din teste, vom avea $N ≤ 11$.
* Pentru alte $20%$ din teste, rezultatul poate fi reprezentat pe $64$ de biţi cu semn.
h2. Exemplu
table(example). |_. petrecere.in |_. petrecere.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
| 2
|
table(example).
| 3
| 4
|
h3. Explicaţie
...
Pentru primul exemplu, configuraţiile de dans sunt:
$(1, 1) (2, 2)$
$(1, 2) (2, 1)$
Pentru al doilea exemplu, configuraţiile de dans sunt:
$(1, 1) (2, 2) (3, 3)$
$(1, 1) (2, 3) (3, 2)$
$(1, 2) (2, 1) (3, 3)$
$(1, 3) (2, 2) (3, 1)$
== include(page="template/taskfooter" task_id="petrecere") ==
