|
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: Rafaelo
|
Mirko i Slavko su dobili na poklon nekoliko kutija rafelo kuglica. Da se ne bi posvađali oko raspodele, Mirko je predložio sledeće: naizmenično će uzimati (i jesti) po
jednu rafaelo kuglicu iz proizvoljne kutije, i onaj ko uzme poslednju kuglu iz neke kutije dobija kao nagradu sve preostale kuglice. Pošto je Mirko predložio način raspodele,
Slavko ima prednost da bira da li će prvi početi da uzima, ili će to zadovoljstvo prepustiti Mirku. Naravno, Slavko želi da pojede što više kuglica, pa je na vama da mu
došapnete šta da radi (da li da uzima prvi ili drugi). Pretpostavlja se da i Mirko i Slavko uzimaju tako da pojedu što je više moguće kuglica.
Ulaz:
(Ulazni podaci se nalaze u datoteci rafaelo.in) Ulazna datoteka sadrži tačno tri test primera. Svaki od prva tri reda ulazne datoteke sadrži sledeće podatke: broj kutija
K ( 2 ≤ K ≤ 50 ), a zatim K brojeva iz opsega [1, 100] (oni predstavljaju količine kuglica u kutijama).
Izlaz:
(Izlazne podatke upisati u datoteku rafaelo.out) Za svaki od tri test primera iz
ulazne datoteke, u poseban red izlazne datoteke ispisati 1 ako Slavko treba da uzima prvi,
odnosno 2 ako treba da uzima drugi.
Primer 1:
rafaelo.in
|
|
rafaelo.out
|
2 2 2
3 3 2 1
4 3 2 3 3
|
|
2
1
1
|
Objašnjenje.
Važi sledeće:
- kombinacija - iz koje god kutije prvi da uzme, u toj kutiji će ostati 1 kugilca, koju
onda uzima drugi i time dobija i sve ostale kuglice
- kombinacija - prvi može odmah da uzme kuglicu iz poslednje kutije, i time dobija
sve ostale kuglice
- kombinacija - ukoliko neko uzme kuglicu iz kutije koja ima 2 kugle, tada drugi
dobija sve ostale. Naizmeničnim uzimanjem iz kutije koja ima 3 kugle, dobijamo da
prvi može da pojede više.
|
|
fajl: rafaelo.cpp
|
/*
*
* Rafaelo kuglice, orkuzno 2008/09
*
* Autor : Rajko Nenadov (rajkon@gmail.com)
*
*/
#include <cstdio>
using namespace std;
// najveci broj kutija
const int MaxK = 51;
int K;
int kuglice[MaxK];
int resenje[3];
int main()
{
FILE *f;
f = fopen("rafaelo.in", "r");
for (int test = 0; test < 3; test++)
{
fscanf(f, "%d", &K);
for (int i = 0; i < K; i++)
fscanf(f, "%d", &kuglice[i]);
// ukoliko neka kutija sadrzija 1 kuglicu, vishe ce pojesti prvi igrac
bool jedna = false;
for (int i = 0; !jedna && i < K; i++)
if (kuglice[i] == 1)
jedna = true;
if (jedna)
resenje[test] = 1;
else
{
// inace, prvi pobedjuje ako je ukupan broj kuglica neparan
// a drugi ako je paran.
// objasnjenje :
// ukoliko neki igrac uzme kuglicu iz kutije u kojoj ima 2 kuglice, pobedjuje njegov protivnik.
// kako na pocetku svaka kutija ima bar 2 kuglice, oni ce naizmenicno uzimati (redosled nije bitan) iz kutije koja ima vise od 2 kuglice.
// kada se dodje do situacije da se u svakoj kutiji nalaze tacno 2 kuglice, gubi igrac koji je na potezu.
// dakle, ukupan broj poteza koji ce se napraviti pre nego sto se dodje do te situacije je :
// (kuglice[0] - 2) + ... + (kuglice[K-1] - 2)
// ukoliko je taj broj paran, znaci da je sledeci na potezu prvi igrac, i da on gubi;
// ukoliko je neparan, sledeci na potezu je drugi igrac, i onda on gubi.
int suma = 0;
for (int i = 0; i < K; i++)
suma += kuglice[i] - 2;
if (suma % 2 == 0)
resenje[test] = 2;
else
resenje[test] = 1;
}
}
fclose(f);
f = fopen("rafaelo.out", "w");
for (int test = 0; test < 3; test++)
fprintf(f, "%d\n", resenje[test]);
fclose(f);
return 0;
}
|
|
|