Zadanie

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 kamnieok 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á?

Úloha

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.

Formát vstupu

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.

Formát výstupu

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.

Hodnotenie

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).

Príklad

Input:

5
15 12 11 3 1

Output:

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čí.)

Input:

4
100 20 20 20

Output:

Jitka 40

(Začína Jitka a zoberie 100, zvyšok uz Marcelovi stačiť nebude.)

Input:

2
7 7

Output:

Remiza

Na vstupe sme dostali už utriedenú postupnosť, takže jediné čo potrebujeme spraviť je odsimulovať hru Jitky a Marcela. Jeden z problémov, na ktorý sme mohli naraziť je že súčet hmotností kamienkov je veľmi veľký. Tento súčet sa nezmestí do bežnej premennej v C++ alebo Pascale. V tomto príklade mali výhodu riešitelia, ktorí programovali v Pythone, pretože v Pythone majú celočíselné premenné ľubovolný rozsah. V ostatných jazykoch stačilo však použiť 64 bitové premenné (do ktorých sa tento súčet zmestí) a všetko bolo v poriadku.

Časová aj pamäťová zložitosť tohto algoritmu je lineárna v závislosti od \(n\), čo zapisujeme ako \(O(n)\), pretože iba v jednom cykle spočítame súčet hmotností kamienkov pre Jitku a Marcela a sčítavanie je konštantná operácia.

n = int(input())
k = map(int, input().split())

j, m = 0, 0
for x in k:
  if j <= m:
    j += x
  else:
    m += x

if j == m:
  print('Remiza')
elif j < m:
  print(f'Marcel {m - j}')
else:
  print(f'Jitka {j - m}')
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;

  vector<int> k(n);
  for (int i = 0; i < n; i++) cin >> k[i];

  long long j = 0, m = 0;
  for (int i = 0; i < n; i++) {
    if (j <= m) j += k[i];
    else m += k[i];
  }

  if (j == m) cout << "Remiza";
  else if (j > m) cout << "Jitka " << j - m;
  else cout << "Marcel " << m - j;
  cout << endl;
}

Iné riešenie

Problému s veľkými číslami sa dalo vyhnúť ak sme si v programe počítali iba rozdiel skóre. Stačí si uvedomiť, že v ľubovolnom momente počas behu programu tento rozdiel nemôže byť v absolútnej hodnote väčší ako najťažší kamienok (lebo inak by musel vyberať kamienok hráč s väčším skóre).

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;

  vector<int> k(n);
  for (int i = 0; i < n; i++) cin >> k[i];

  int diff = 0;
  for (int i = 0; i < n; i++) {
    if (diff <= 0) diff += k[i];
    else diff -= k[i];
  }

  if (diff == 0) cout << "Remiza";
  else if (diff > 0) cout << "Jitka " << diff;
  else cout << "Marcel " << -diff;
  cout << endl;
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.