Fişierul intrare/ieşire:copii.in, copii.outSursăAlgoritmiada 2010, Runda 4
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incopii.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content