Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Emovi na [email protected]
Jitka a Marcel sa išli spolu hrať von na pieskovisko. Po hodine ich to však prestalo baviť, veď už sú dospelí! A veľké deti sa nehrajú na pieskovisku, hrajú sa na štrkovisku. Pobrali si svoje formičky a vybrali sa na neďaleké štrkovisko. No zábava im ani tam nevydržala dlho – skúšali ste robiť pieskový koláčik zo štrku?
Našťastie dostala Jitka nápad na novú hru. Najprv si pozbierali nejaký počet kamienkov a zoradili ich do postupnosti podľa hmotnosti (Marcel je veľmi citlivý človek, a dokáže bezchybne porovnať váhu ľubuvoľných dvoch kamienkov). Následne brali rad radom kamienky, začnúc najťažším. Kamienok si vždy bral hráč, ktorý mal v tom čase menší súčet hmotností kamienkov, poprípade, ak ich kôpky mali rovnakú hmotnosť, vyberala Jitka (dámy majú prednosť). Po zobratí posledného kamienku vyhral hráč s väčším súčtom hmotností.
Ako prvá si kamienok berie Jitka, keďže obaja majú vtedy súčet hmotností 0 a pamätáte sa, ako je to s tou prednosťou.
S veľkým počtom kamienkov však hra trvá dlho. Vedeli by ste im preto pomôcť napísať program, ktorý by zistil, kto z hráčov vyhrá?
Na vstupe je zostupne usporiadaná postupnosť čísel. Jitka a Marcel sa hrajú hru, pri ktorej postupne berú čísla z postupnosti (začínajúc najväčším). V každom ťahu berie hráč s menším súčtom. Na začiatku alebo v prípade, že majú rovnaký súčet berie Jitka. Vašou úlohou je zistiť, ktorý hráč vyhrá a s akým náskokom.
Na prvom riadku vstupu dostanete číslo $n$ ($1 \leq n \leq 10^5$).
Na druhom riadku je $n$ čísel $k_1$ až $k_n$ – hmotnosti jednotlivých kamienkov. Platí, že $1 \leq k_i \leq 10^6$ a tieto hodnoty sú na vstupe zoradené od najväčších čísel po najmenšie.
Na jediný riadok výstupu vypíšte meno víťazného hráča (Jitka alebo Marcel) a medzerou oddelený
náskok s akým daný hráč vyhral. V prípade remízy vypíšte Remiza.
Príklad obsahuje $5$ sád vstupov. Za každú je možné získať najviac $3$ body. V prvých troch sadách platí $n \leq 1\,000$.
Tip: Súčty hmotností kamienkov v poslednej sade môžu byť veľmi veľké čísla. Preto si treba uvedomiť, že v niektorých jazykoch majú bežné celočíselné premenné obmedzený rozsah. Napríklad v C++
int má klasicky 32 bitov, čo nemusí stačiť. Chcete preto použiť 64 bitové premenné (napr. long long v C++, Int64 v Pascale).
5
15 12 11 3 1
Marcel 4
(Začína Jitka a zoberie kameň hmotnosti 15, potom ďalšie dva kamene zoberie Marcel. Zvyšok už zoberie Jitka, ale to jej na víťazstvo nestačí.)
4
100 20 20 20
Jitka 40
(Začína Jitka a zoberie 100, zvyšok uz Marcelovi stačiť nebude.)
2
7 7
Remiza