Fişierul intrare/ieşire: | rute.in, rute.out | Sursă | Romanian Open Contest, TIMUS 2001 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rute
Un turist roman a plecat intr-o excursie pe Marea Mediterana. El a ajuns intr-unul dintre orasele de pe una din cele 3 insule pe care doreste sa le viziteze. Fiecare insula are exact N orase si toate sunt porturi. Turistul doreste sa isi inceapa calatoria din orasul in care se afla, sa viziteze toate celelalte 3*N-1 orase exact o data si apoi sa se intoarca in orasul de unde si-a inceput calatoria, pentru a pleca dupa aceea inapoi spre casa.
Din pacate, pe fiecare din cele 3 insule traiesc triburi de canibali, astfel incat este interzis de catre autoritati sa se calatoreasca direct intre 2 orase de pe aceeasi insula. Din fericire, exista rute maritime intre orice pereche de orase care nu se afla pe aceeasi insula. Nu exista rute maritime intre 2 orase de pe aceeasi insula.
Turistul vrea sa stie in cate moduri isi poate planifica calatoria pe cele 3 insule.
Date de intrare
Fisierul de intrare rute.in contine un singur numar intreg N, reprezentand numarul de orase de pe fiecare din cele 3 insule.
Date de iesire
In fisierul de iesire rute.out veti afisa numarul de posibilitati de planificare a calatoriei. 2 calatorii se considera identice daca secventa de 3*N orase vizitate este identica sau daca secventa oraselor vizitate in cadrul primei calatorii este identica cu secventa oraselor vizitate in a doua calatorie, dar citita invers (de exemplu, daca fiecare insula ar avea un singur oras, numerotat cu numarul insulei, calatoriile 1-2-3-1 si 1-3-2-1 ar fi identice).
Restrictii
- 1 ≤ N ≤ 30
Exemplu
rute.in | rute.out |
---|---|
2 | 16 |