.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » gramada

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
gramada


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Exista multe jocuri cu gramezi de pietre, chibrituri sau alte obiecte mici pe care le vom numi piese, din care unul sau mai multi jucatori iau piese dupa anumite reguli, operatie pe care o vom numi mutare. Unul dintre cele mai simple jocuri intre doua persoane foloseste o singura gramada, din care jucatorii iau alternativ piese dupa urmatoarele reguli : 
- cel care incepe jocul poate lua oricate piese, dar nu toate
- jucatorul care urmeaza la mutare trebuie sa ia cel putin o piesa
- daca un jucator a luat k piese, cel care urmeaza poate lua cel mult 2k piese
- cel care ia toate piesele ramase in gramada castiga jocul.
Calculatorul va invita la un astfel de joc; el fiind un foarte bun jucator va ofera sansa de a face prima mutare.

Cerinta

Cunoscand numarul N de piese din gramada, determinati numarul de piese pe care trebuie sa-l luati prima data pentru a fi siguri de castig, indiferent de jocul calculatorului.

Date de intrare

In fisierul de intrare gramada.in este scris numarul intreg N.

Date de iesire

In fisierul gramada.out veti scrie numarul 0 daca oricum ati incepe jocul (oricate piese ati lua la prima mutare) calculatorul va castiga. In caz ca aveti o strategie de castig, veti scrie un numar natural nenul care sa reprezinte  numarul pieselor pe care il luati prima data, astfel ca la orice raspuns al calculatorului sa puteti castiga. Daca exista mai multe mutari castigatoare veti scrie mutarea in care luati numarul maxim de piese.

Restrictii

  • 1 < N <= 1000000000

Exemple

gramada.in gramada.out Explicatie
10 2

Daca luati 4 sau mai multe piese, calculatorul ia tot
Daca luati 3 piese, calculatorul ia doua, apoi castiga
Daca luati o piesa, calculatorul ia tot una si castiga
Numai daca luati doua piese calculatorul nu are nici o mutare castigatoare

gramada.in gramada.out Explicatie
5 0

Daca luati o piesa, calculatorul ia tot una
Daca luati mai mult de una, calculatorul le ia pe toate

 

gramada.in gramada.out
1000 13

prof. Nistor Mot
Colegiul National "N.Balcescu" - Braila

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor