Prorok
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 0,3 s | 64 Mb | standardni izlaz | standardni ulaz |
Nakon što je proveo ceo dan gledajući naučnofantastične filmove, Petar je odlučio da iskoristi ideje i znanje koje je iz njih pokupio i napravi mehaničkog proroka, odnosno mašinu koja odgovara na bilo kakvo da-ne pitanje koje joj se postavi.
Nakon što je napravio proroka, Petar mu je postavio pitanja i beležio odgovore koje je dobio. Da ne bi trošio previše papira, svako pitanje je skraćeno obeležio identifikacionim brojem (tako da istim brojevima odgovara isto pitanje -- Petar je neka pitanja postavio više puta). Primetio je da su odgovori koje je dobio kontradiktorni, tj. da je na neka pitanja dobio i odgovor "da" i odgovor "ne".
Petar pretpostavlja da je problem u neispravnoj prostor-vremenskoj ferfucni, zbog koje prorok na svako -to postavljeno pitanje odgovara suprotno od tačnog odgovora (gde ). Da bi mogao da počne popravke odmah, umesto da čeka da sazna prave odgovore, zamolio vas je da nađete najmanje koje odgovara ovoj pretpostavci i dobijenim odgovorima.
Opis ulaza
U prvom redu standardnog ulaza nalazi se jedan prirodan broj -- broj pitanja koja je Petar postavio. U narednih redova nalaze se identifikacioni broj -tog pitanja i odgovor koji je prorok dao . Sve vrednosti će biti ili "da" ili "ne".
Opis izlaza
U prvom i jedinom redu standardnog izlaza ispisati -- najmanju vrednost "perioda" sa kojim je moguće da prorok greši. Ukoliko takvo ne postoji, ispisati -1.
Primeri
1 da
2 ne
1 ne
3 da
2 ne 3
1 da
1 ne
1 ne -1
Objašnjenje primera
U prvom primeru, ako su odgovori na pitanja sa identifikacionim brojevima redom "da", "ne" i "da", odgovori proroka su konzistentni ako je na treće postavljeno pitanje dao suprotan odgovor (tj. ). Za se ne slažu odgovori na prvo i treće pitanje (prorok na njih ne bi odgovorio suprotno), kao ni odgovori na drugo i peto (prorok bi na drugo pitanje odgovorio suprotno a ne peto ne bi).
Ograničenja i podzadaci
Postoje podzadataka, u kojima dodatno važi:
- Podzadatak 1 [20 poena]: .
- Podzadatak 2 [35 poena]: , i za sve važi .
- Podzadatak 3 [45 poena]: .
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.