ACM RTK - 1. skupina

Izštevanka

Otroci so se že malo naveličali vsakokrat uporabljati preprosto izštevanko ››An ban pet podgan‹‹ za določitev tistega, ki lovi, zato so se odločili za manjšo spremembo: vsak naj ima dve življenji, kdor ostane brez, je ››izbrani‹‹.

V krog se postavi n otrok, vsak stoji z obema nogama na tleh (t.j. ima dve življenji). Naj bodo oštevilčeni z zaporednimi številkami od 1 do n. Začnemo pri otroku številka 1 in od njega naredimo k korakov po krogu (pri tem torej njega ne štejemo, ampak štejemo šele otroke od 2 naprej) — k je pozitivno celo število, lahko je tudi večje od n. Otrok na tako določenem mestu mora dvigniti nogo (izgubi eno življenje). Če mora dvigniti še drugo in zato pasti, je izštevanke konec in ta otrok postane ››izbrani‹‹. Če pa še vedno stoji na eni nogi (je pravkar izgubil šele prvo življenje), se izštevanka nadaljuje (spet začne šteti) pri otroku neposredno za njim, hkrati pa izštevanko podaljšamo za eno besedo, torej povečamo k za 1.

Napiši program, ki bo prebral dve pozitivni celi števili — n in začetno vrednost k, opravil korake izštevanke in izpisal številko ››izbranega‹‹ otroka, to je tistega, ki je padel po tleh, ker je izgubil obe življenji. Število otrok n je vsaj 1 in kvečjemu 100.

Primer: če imamo n = 5 in k = 3, morajo po vrsti dvigovati noge otroci 4, 3, 3 in igre je konec — izbran je otrok številka 3.