Spēlētāju rangs

ID: rangs
Grūtība: 3/5
Laika limits: 1

Uzdevums

Turnīrā N spēlētāji kopumā ir nospēlējuši K spēles. Katrā spēlē piedalās divi spēlētāji. Katrs spēlētājs var būt nospēlējis atšķirīgu spēļu skaitu, bet nekādi divi spēlētāji nav savā starpā izspēlējuši vairāk par vienu spēli. Iespējams pat, ka kāds spēlētājs nav izspēlējis vispār nevienu spēli. Nevienā spēlē nav iespējams neizšķirts - katrs spēlētājs vai nu spēli uzvar, vai tajā zaudē.

Pēc spēļu rezultātiem tiek noteikts spēlētāju rangs. Viena no situācijām, kad spēlētāju rangu noteikt nav iespējams, ir tad, ja vairāk kā divi spēlētāji ir uzvarējuši cikliskā secībā. Piemēram, ja spēlētājs A ir uzvarējis spēlētāju B, spēlētājs B - spēlētāju C, spēlētājs C - spēlētāju A, tad šo spēlētāju rangu noteikt nav iespējams.

Protams, katrs spēlētājs var but iesaistīts vairāk kā vienā šādā ciklisku uzvaru virknē. Šajā uzdevumā neinteresēsimies par citiem iemesliem, kas liedz noteikt spēlētāju rangu - piemēram, ja spēlētājs nav izspēlējis nevienu spēli.

Uzrakstiet programmu, kas dotiem spēļu rezultātiem nosaka to spēlētāju skaitu, kuru rangu nav iespējams noteikt tāpēc, ka katrs no šiem spēlētājiem ir kādā ciklisku uzvaru virknē!

 

Ievaddati

Teksta faila rangs.dat pirmajā rindā dotas divu naturālu skaitļu N (2 ≤ N ≤ 20) un K (1 ≤ K ≤ 30) vērtības, kas atdalītas ar tukšumsimbolu. Spēlētāji ir numurēti pēc kārtas ar skaitļiem no 1 līdz N. Katrā no nākošajām K faila rindām ir dota informācija par vienu spēli un satur četrus veselus nenegatīvus skaitļus a b sa sb , kur katrus divus blakus skaitļus atdala tukšumsimbols. a un b ir spēlētāju numuri, un sa un sb ir katra spēlētāja (atticīgi a un b) iegūto punktu skaits. Iegūto punktu skaits nepārsniedz 10 un spēlētājs, kas ieguvis vairāk punktu, ir uzvarējis.

 

Izvaddati

Teksta faila rangs.rez vienīgajā rindā jāizvada vesels skaitlis - to spēlētāju skaits, kuru rangu nav iespējams noteikt cikliskās uzvaru virknes dēļ.

 

Piemērs

rangs.datrangs.rez
10 12
1 8 2 1
1 2 5 0
10 7 1 2
6 9 6 9
3 4 3 1
9 5 3 1
8 2 6 8
4 9 3 0
4 1 5 2
6 10 3 5
3 5 1 9
6 7 9 8 
7
Spēlētāji 3, 4, 5 un 9 atrodas vienā, bet 6,7 un 10 - otrā ciklā.
  
rangs.datrangs.rez
5 3 
1 3 9 7
5 1 9 2
3 5 2 0 
3
Spēlētāji 1, 3 un 5 atrodas ciklā, bet 2 un 4 nav spēlējuši.
  
rangs.datrangs.rez
5 6 
1 2 2 1
1 5 2 1
1 3 2 1
5 2 0 5
5 3 1 8
2 4 4 2 
0
Neviens spēlētājs neatrodas ciklisko uzvaru virknē.
  
rangs.datrangs.rez
10 5
2 4 0 2
2 6 5 3
8 2 8 2
6 4 6 2
8 6 0 2 
4
Spēlētāji 2, 4 un 6 atrodas vienā, bet 2, 6 un 8 - otrā ciklā, līdz ar to ciklos pavisam iesaistīti četri spēlētāji.

 

Atsauces

Uzdevums izmantots informātikas olimpiādē NOI2001.
© 2001-2002 olimps! http://www.lio.lv/olimps/