Igra sa brojevima
vreme | memorija | ulaz | izlaz |
---|---|---|---|
1 s | 64 Mb | standardni izlaz | standardni ulaz |
Na papiru je napisan broj N. Dva igrača naizmenično rade sledeće: igrač koji je na potezu bira neki delilac broja koji je napisan na papiru (delilac ne sme biti 1 ili broj sa papira), računa količnik broja sa papira i izabranog delioca, briše broj koji se nalazi na papiru i piše dobijeni količnik. Ukoliko igrač ne može da odigra svoj potez (tj. jedini delioci su 1 i broj sa papira), on je pobednik. Napisati program koji treba da učita niz brojeva i za svaki od tih brojeva odredi koji igrač pobeđuje u partiji na čijem početku se na papiru nalazi taj broj. Smatrati da oba igrača igraju optimalno (povlače najbolje poteze).
U prvom redu standardnog ulaza nalazi se broj M. U narednih M redova se nalazi po jedan broj Ni.
Na standardni izlaz treba ispisati M redova. U i-tom redu ispisati broj 1, ako prvi igrač pobeđuje kad je početni broj na papiru Ni, odnosno ispisati 2 ako drugi igrač tada pobeđuje.
5 ≤ M ≤ 20
1 ≤ Ni ≤ 10.000.000
5 1 4 5 10 25
1 2 1 2 2
M = 5 i potrebno je ispitati ko pobeđuje za svaki od početnih brojeva 1, 4, 5, 10 i 25. Ukoliko je npr. početni broj na papiru 1, prvi igrač ne može odigrati potez pa je (prema pravilima) pobednik. Ako je početni broj na papiru 4, tada prvi može odigrati samo jedan potez: izabrati delilac 2. Posle toga na papiru ostaje broj 4 : 2 = 2 i u toj situaciju drugi ne može da odigra potez (ne postoji delilac broja 2 različit od 1 i 2) pa je drugi pobedio. Ostala tri slučaja se mogu slično analizirati.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.