.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » na

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
na


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

In ultimul timp, Balaurul Arhirel se joaca cu cei 100 de balauri de la el din cartier un joc inventat de Arhirel. Jocul NA are N piese si se joaca astfel: la inceputul jocului, fiecare piesa se numeroteaza (de la 1 la N) si se trag la sorti legaturile dintre piese. Legaturile sunt intr-o singura directie. Se poate totusi sa exista 2 legaturi intre 2 piese, dar de directii opuse.
Scopul jocului este formarea de cat mai multe configuratii cu aceste N piese. Fiecare jucator incearca pe rand sa formeze o configuratie care nu a mai fost pana in acel moment.
O configuratie se formeaza in urmatorul fel. Se incepe cu piesa 1 tot timpul. De la aceasta se alege o piesa care e legata direct de piesa 1, adica exista o legatura de la piesa 1 la ea. Se retine aceasta legatura (ea formeaza configuratia). Urmatorii pasi constau in alegerea de piese noi (care nu au fost inca alese) care sunt legate direct de una dintre piesele alese, adica exista o legatura de la una dintre piesele alese la ea. Se retin toate legaturile folosite. Procedeul se repeta pana cand toate cele N piese au fost luate.
Configuratia este practic data de cele N-1 legaturi folosite.
Toti balaurii din cartieri sunt tari la informatica, asa ca nimeni nu o sa aiba probleme sa gaseasca o configuratie noua. Problema e ca la un moment dat chiar nu mai sunt alte configuratii, iar cel care castiga este cel care formeaza ultima configuratie posibila.
B.A. vrea tot timpul sa castige, asa ca va cere ajutorul ca sa stie unde sa se aseze si vrea sa stie restul impartirii numarului de configuratii la 101.

Cerinta

Ajutati-l pe Balaurul Arhirel sa castige, adica aflati numarul de configuratii modulo 101.

Date de intrare

Pe prima linie a fisierului na.in se afla un numar natural N reprezentand numarul de piese. Pe urmatoarele N linii se afla cate N cifre binare, reprezentand legaturile. Practic, a j-a cifra de pe linia i reprezinta daca exista legatura de la piesa i la piesa j. 0 inseamna ca nu exista legatura, iar 1 inseamna ca exista.

Date de iesire

Fisierul na.out va contine o linie cu un singur numar, si anume numarul de configuratii modulo 101.

Restrictii si precizari

  • 2 < N < 101
  • Exista tot timpul cel putin o configuratie
  • Nu exista legaturi de la o piesa la ea insasi

Exemplu

na.in

na.out

Explicatii

3
0 1 1
1 0 1
1 1 0


3

Exista 3 configuratii:

1: 1 -> 2, 2 -> 3
2: 1 -> 3, 3 -> 2
3: 1 -> 2, 1 -> 3

Marius Andrei
Universitatea Politehnica Bucuresti
Contact: marsamg@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: conflicte, cadere, leaves, distanta, ivv, aparitii, tabara1, stop, hanoi, logn, cuburi1, viteza, masina3, anticip, cabane, spp, regine, comoara2, perle, cuvinte1, sortari, triti
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor