== include(page="template/taskheader" task_id="otilia") ==
==Include(page="template/taskheader" task_id="otilia")==
Poveste ...
Otilia si Burbucel, fiind in fata unei gramezi de $N$ pietre si neavand ce face, stabilesc regulile unui nou joc. Cei doi copii vor ca jocul sa fie simplu asa ca impun doar trei reguli:
1. Primul jucator are voie sa ia din gramada cel mult $K$ piese
2. Cu exceptia primei mutari, fiecare jucator are voie sa ia maxim $P*t$ pietre, unde $t$ este numarul de pietre care au fost substituite din gramada la mutarea precedenta
3. Pierde cel care muta ultimul (cel care ia ultimele pietre din gramada)
Cei doi au jucat multe jocuri, Burbucel fiind intotdeauna cel care alege numerele $N, K$ si $P$ si Otilia primul jucator care muta. Otilia a observat ca alegerile lui Burbucel se repeta dupa $M$ jocuri (alegerea numarul $M+1$ este identica cu alegerea numarul $1$, alegerea numarul $M+2$ este identica cu alegerea numarul $2$, etc.). Ea ar vrea sa stie daca poate castiga sau nu pentru fiecare dintre primele M alegeri ale lui Burbucel. Motivul este usor de intuit: Otilia nu vrea sa-i dea ocazia lui Burbucel sa castige asa ca va renunta pe jocurile unde nu are strategie de castig.
h2. Cerinta
...
Scrieti un program care rezolva dilema Otiliei.
h2. Restrictii
h2. Date de Intrare
...
Pe prima linie a fisierului $otilia.in$ se afla $M$, numarul de alegeri ale lui Burbucel. Urmatoarele $M$ linii contin cate trei numere, $N, K si P$ reprezentand o alegere a lui Burbucel ({$N$} - numarul de pietre din gramada, $K$ - numarul maxim de pietre pe care le poate lua Otilia la prima mutare, $P$ - factorul cu care se inmulteste numarul de pietre luate la mutarea precedenta rezultand astfel numarul maxim de pietre care se pot substitui la mutarea curenta).
h2. Date de intrare
h2. Date de Iesire
...
Fisierul $otilia.out$ contine $M$ linii, pe linia $i$ aflandu-se $1$ daca Otilia castiga la alegerea numarul $i$ a lui Burbucel sau $0$ daca ea pierde (alegerile sunt numerotate de la $1$ la $M$ in ordinea in care se gasesc in fisierul de intrare).
h2. Date de iesire
h2. Restrictii
...
* $1 ≤ M ≤ 30 000$
* $1 ≤ N ≤ 5 000 000$
* $1 ≤ K ≤ N$
* $1 ≤ P ≤ 10$
* Pentru $50%$ din teste $N ≤ 500 000$ pentru toate alegerile lui Burbucel
h2. Exemplu
| otilia.in | otilia.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. otilia.in |_. otilia.out |
|4
1 1 3
3 2 8
5 1 3
100 1 1
|0
1
0
1|
== include(page="template/taskfooter" task_id="otilia") ==
==Include(page="template/taskfooter" task_id="otilia")==
