apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

sledzi Slēdži 10 sek.


 Uzdevums

Deivam ir vecs televizors, un daži tā slēdži darbojas nepareizi. Kamēr televizors bija jauns, slēdža ieslēgšana izslēdza visus pārējos slēdžus, tādējādi ieslēgts palika tikai viens slēdzis.

Tagad slēdža ieslēgšana izslēdz tikai dažus slēdžus, bet pārējo slēdžu stāvoklis mainīts netiek. Deivs par katru slēdzi zina tā iedarbību uz pārējiem slēdžiem.

Uzrakstiet programmu, kas palīdzēs Deivam noteikt, kādu mazāko skaitu slēdžu secīgi jāieslēdz, lai no dotās sākotnējās slēdžu konfigurācijas iegūtu tādu, kurā slēdzis ar numuru 3 ir ieslēgts, bet visi pārējie - izslēgti!

 
 Ievaddati

Teksta faila sledzi.dat pirmajā rindā dots vesels skaitlis N, 3 ≤ N ≤ 20, - televizora slēdžu skaits. Slēdži ir sanumurēti ar skaitļiem no 1 līdz N.

Otrajā rindā doti N bināri cipari, kuri nosaka slēdžu sākotnējo konfigurāciju - 0 nozīmē, ka atbilstošais slēdzis ir izslēgts, bet 1 - ieslēgts.

Nākamajās N rindās ir dota informācija par slēdžu iedarbību uz pārējiem slēdžiem. (M+2)-ā rinda sākas ar skaitli K, kam seko K augošā secībā sakārtoti skaitļi - to slēdžu numuri, kuri izslēdzas, ieslēdzot slēdzi ar numuru M. Slēdža ieslēgšanas rezultātā nevar izslēgties pats tikko ieslēgtais slēdzis. Ir pieļaujama situācija, ka slēdzis neizslēdz nevienu citu slēdzi.

Visi blakusskaitļi failā atdalīti ar tukšumsimbolu. Zināms, ka dotajiem ievaddatiem vienmēr eksistē atrisinājums.

 
 Izvaddati

Teksta faila sledzi.rez vienīgajā rindā jāizvada vesels skaitlis - mazākais skaits slēdžu, kuri secīgi jāieslēdz, lai no sākotnējās slēdžu konfigurācijas iegūtu tādu, kurā slēdzis ar numuru 3 ir ieslēgts, bet visi pārējie - izslēgti.

 
 Piemērs

sledzi.datsledzi.rez
3
1 1 0
2 2 3
2 1 3
2 1 2
1
  
sledzi.datsledzi.rez
4
0 1 0 1
3 2 3 4
1 1
1 1
0
2
  
sledzi.datsledzi.rez
5
1 1 0 0 1
4 2 3 4 5
4 1 3 4 5
2 2 4
0
4 1 2 3 4
3

 
 Atsauces
Uzdevums izmantots Horvātijas informātikas olimpiādē 2004.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS