TAKMIČENJA IZ PROGRAMIRANJA


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.

igra.cpp    571 b      izvorni kod rešenja
igra.tests.rar    1,815 b      test primeri

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;
}