Županijska razina 2018. / Osnovna škola (6. razred) - 3. zadatak

Svjetsko prvenstvo u nogometu, 22. po redu, održat će se 2022. godine u Kataru, maloj bogatoj državi na Arapskom poluotoku u jugozapadnoj Aziji. Dok mi sanjamo to prvenstvo i priželjkujemo nekog novog Ćiru, organizatori muke muče s velikim vrućinama koje su karakteristične za tu zemlju. Zbog toga su krenuli klimatizirati svoje stadione.

Na centralni stadion postavili su N klima uređaja označenih brojevima od 1 do N. Zbog uštede, kupili su samo jedan daljinski upravljač kojim mogu paliti i gasiti te klime. Problem je što daljinski naizmjence šalje samo dvije vrste signala: prvo šalje signal P koji pali klimu ako je ona ugašena, a onda šalje signal G koji gasi klimu ako je ona upaljena. U slučaju kad signal P usmjerimo prema upaljenoj klimi ili signal G prema ugašenoj klimi ništa se neće dogoditi.

Zlatko je dobio zadatak da isproba klime na stadionu. U početku, sve su klime ugašene. Ako znamo u koje je klime redom Zlatko usmjerio daljinski i poslao signal, ispiši koliko će klima nakon X poslanih signala biti upaljeno.

Nakon tih X poslanih signala, Zlatko se zapitao koliko još minimalno signala treba uputiti prema klimama po svom odabiru da bi sve klime bile upaljene.

Ulazni podaci

• U prvom retku nalazi se broj N (1 ≤ N ≤ 100), broj klima uređaja iz teksta zadatka.
• U drugom retku nalazi se broj X (1 ≤ X ≤ 1000), broj poslanih signala iz teksta zadatka.
• U sljedećih X redaka nalazi se po jedan prirodan broj Si (1 ≤ Si ≤ N), oznaka klime u čijem je smjeru upućen i-ti poslani signal.

Izlazni podaci

• U prvi redak treba ispisati broj upaljenih klima nakon X poslanih signala.
• U drugi redak treba ispisati minimalni broj signala iz teksta zadatka.

Primjeri test podataka

Ulaz

3 
5
1
2 
3 
1 
2

Izlaz

2
2

Objašnjenje

Prvi poslani signal (P) je upalio klimu „1“, drugi signal (G) nije djelovao na klimu „2“, treći signal (P) je upalio klimu „3“, četvrti (G) je ugasio klimu „1“, a peti (P) je upalio klimu „2“. Na kraju će raditi samo klime „2“ i „3“. Još najmanje dva puta bit će potrebno uputiti signal prema klimi „1“ da bi se i ona upalila.

Ulaz

3
5 
1 
1 
1 
1 
1

Izlaz

1
4

Ulaz

3 
6 
1 
1 
2 
2 
3 
3

Izlaz

0 
5