Šeštadieninė informatikos olimpiadininkų mokykla

Tarkime, kad jūs gavote šitokį laišką: Dalyvaudamas šiame žaidime laimėsite 15 624 litus. Tam laiško pabaigoje parašytu paskutiniuoju (šeštuoju) adresu išsiųskite 1 litą ir šį adresą išbraukite. Savo adresą įrašykite pradžioje, adresus pernumeruokite. Pataisytą laišką perrašykite ir išsiųskite penkiems savo pažįstamiems.

Penki pažįstami, gavę jūsų laiškus, išbrauks paskutinius adresus, o savuosius įrašys pradžioje. Jūsų adresas taps antruoju laiškuose. Žaidimas tęsis. Jūsų adresas trečiuoju numeriu bus laiškuose, ketvirtuoju – , penktuoju – ir šeštuoju – 15 625 laiškuose. Štai čia jūs ir praturtėsite, gavę 15 625 litus. Atėmus žaidimo pradžioje investuotą litą, turėsite 15 624 litus pelno.

Tokie ar panašūs laiškai jau yra ne kartą keliavę po pasaulį. Tarkime, pilietis nutarė pradėti žaidimą ir įrašė savo adresą pirmuoju numeriu . Jis susitarė su dar penkiais draugais ir įrašė jų adresus – numeriais.

Praėjus šešiems laiškų rašymo ciklams žaidėjas tikėjosi gauti 15 625 litus, žaidėjas – 3125 litus, žaidėjas – 625 litus, – 125, – 25 ir – 5 litus. Iš tikrųjų minėti žaidėjai (visi arba keletas jų) gavo mažiau. Mat ne visi, gavę laiškus, norėjo praturtėti ir įsitraukė į žaidimą.

Užduotis

Nagrinėkime bendresnį atvejį, kai laiškuose rašoma adresų ir laiškas siunčiamas žmonių. Cituoto laiško atveju , .

Parašykite algoritmą, kuris rastų, kiek žmonių, gavusių laiškus, pasitraukė iš žaidimo.

Pradiniai duomenys

Pradiniai duomenys – skaičiai , ir kiekvieno žaidėjo, kurio adresas buvo įrašytas pirmame laiške, gautų pinigų sumos ( skaičių).

Laikykite, kad pradiniai duomenys teisingi ir kad visi žaidėjai elgėsi sąžiningai, t. y. rašė laiškus kitiems tik tada, kai išsiuntė po vieną litą nurodytu adresu.

Rezultatai

Rezultatą sudaro vienas skaičius – iš žaidimo pasitraukusių žmonių kiekis.

Pavyzdžiai

6 5
12500 2500 500 100 20 4

1

Ribojimai