| Fişierul intrare/ieşire: | copii.in, copii.out | Sursă | Algoritmiada 2010, Runda 4 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Copii
Laura a plecat în excursie împreună cu N copii. Între unii copii există relaţii de prietenie, dar relaţia de prietenie nu este în mod obligatoriu reciprocă. Laura vrea să organizeze un joc prin care copiii să se cunoască mai bine. Pentru o bună desfăşurare a jocului, ea trebuie sa împartă copiii în mai multe echipe, cel puţin două. Numim mulţimea prietenilor unei echipe mulţimea formată din copiii consideraţi prieteni de cel puţin unul dintre membrii echipei respective. Laura trebuie să împartă copiii astfel încât pentru fiecare echipă, mulţimea prietenilor acestei echipe să conţină cel puţin un copil din fiecare dintre celelalte echipe.
Cerinţă
Cunoscând relaţiile de prietenie dintre copii, determinaţi în câte moduri poate Laura să formeze echipele pentru joc.
Date de intrare
Fişierul de intrare copii.in conţine pe prima linie numărul natural N. Pe următoarele N linii, se află câte N caractere din mulţimea {'0', '1'}. Al j-lea caracter (1 ≤ j ≤ N) de pe linia i+1 (1 ≤ i ≤ N) din fişier este '1' dacă al i-lea copil îl consideră prieten pe cel de-al j-lea copil, respectiv '0', în caz contrar.
Date de ieşire
În fişierul de ieşire copii.out conţine un singur număr natural reprezentând numărul de posibilităţi în care Laura poate să împartă copiii în echipe.
Restricţii
- 1 ≤ N ≤ 10
- Al i-lea caracter de pe linia i (1 ≤ i ≤ N) va fi întotdeauna '0'.
Exemplu
| copii.in | copii.out |
|---|---|
| 3 010 101 110 | 3 |
| 2 01 10 | 1 |
Explicaţie
Pentru primul exemplu, există 3 modalităţi de a împărţi copiii în echipe: (1, 2) (3); (1, 3) (2); (1) (2, 3). Pentru al doilea exemplu, singura modalitate corectă de a împărţi copiii pe echipe este (1) (2).
