|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Igra
|
Na papiru je napisan broj N (1 ≤ N ≤ 107). 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).
Ulaz:
(Ulazni podaci se nalaze u datoteci igra.in) U prvom redu ulazne datoteke se nalazi
broj M (5 ≤ M ≤ 20). U narednih M redova se nalazi po jedan broj Ni (1 ≤ Ni ≤ 107).
Izlaz:
(Izlazne podatke upisati u datoteku igra.out) U izlaznu datoteku treba upisati
M redova. U i-tom redu ispisati broj 1, ako prvi igrač pobeđuje kad je početni broj na
papiru Ni, a 2, ako drugi igrač pobeđuje.
Primer 1:
igra.in
|
|
igra.out
|
5
1
4
5
10
25
|
|
1
2
1
2
2
|
|
|
fajl: igra.cpp
|
#include <iostream>
#include <cstdio>
using namespace std;
int Solve(int n){
int cnt = 0;
for (long k = 2; cnt <= 2 && 2 * k <= n; k++){
long tmp = n;
while (tmp % k == 0){
cnt++;
tmp /= k;
}
}
if (cnt == 2) return 2;
else return 1;
}
int main(){
FILE *f, *fout;
f = fopen("igra.in", "r");
fout = fopen("igra.out", "w");
int test;
fscanf(f, "%ld", &test);
for (int i = 0; i < test; i++){
int n;
fscanf(f, "%ld", &n);
fprintf(fout, "%ld\n", Solve(n));
}
fclose(f); fclose(fout);
return 0;
}
|
|
|