2. Ukladanie kartičiek vzorové riešenie

5
1 3 2 1 4

Vlejd

4
3 3 3 3

John

1
100000

Vlejd

Našou úlohou bolo zistiť pre daný vstup, či existuje výherná stratégia pre prvého hráča. Teda či počnúc prvým ťahom, bez ohľadu na to ako zareaguje John, môže Vlejd spraviť taký ťah že Johna dostane do situácie, z ktorej nemôže vyhrať (ak bude Vlejd hrať dobre).

Kedy Vlejd vyhrá

Ak je v hre jediná kartička s najväčším číslom, je to ideálna situácia, Vlejd ju zoberie a vyhrá. Ak je ale najväčších kartičiek viac, rozlíšujeme dve situácie. Ak je kartičiek nepárny počet, Vlejd opäť zoberie prvú z nich a ďalej budú striedavo brať po jednej kartičke, až zoberie poslednú (John zase nemá na výber ani v jednom ťahu).

Problém nastane ak ich je párny počet. Vtedy Vlejd potrebuje aby prvú z nich zobral John. Znamená to teda že Vlejd je nútený zobrať nejakú z menších kartičiek, aby hneď neprehral. Musí si však dať pozor, aby sa nedostal do situácie, kedy mu John zoberie poslednú menšiu kartičku a on už bude nútený zobrať prvú z najväčších kariet. Jeho cieľom je teda opäť zobrať poslednú kartu, ale teraz zo všetkých okrem najväčších. Dostali sme sa ku problému, ktorý sme už vyššie vyriešili.

Vieme teda, že ak je najväčších kariet nepárny počet, Vlejd vyhrá. Ak je najväčších párny, ale druhých najväčších nepárny, Vlejd taktiež vyhrá. Ak by sme takto pokračovali, zistíme, že ak v postupnosti kartičiek usporiadanej od najväčšej narazíme na nejakú, ktorej je nepárny počet, Vlejd určite vyhrá.

Pozrime sa, ako by teda prebiehala nejaká hra: Karty: 1 2 2 3 3 3 4 4 5 5 5 5 Vlejd: 3 Karty: 3 3 4 4 5 5 5 5 John: ?

Vlejd sa pozrel na kartičky a najväčšia, ktorej je nepárny počet, bola trojka, tak ju zobral. Po takomto ťahu Johnovi ostala každá karta v párnom počte, a neostáva mu nič iné ako to zmeniť a dať Vlejdovi opäť víťaznú pozíciu. Ďalej Vlejdovi stačí ťahať to isté, čo potiahne John.

Vyhrávajúca a prehrávajúca pozícia

Kartičky, ktoré ostávajú na stole budeme volať pozícia v hre. Ak je teda na stole len jedna najväčšia kartička, hráč, ktorý je na ťahu, môže vyhrať, a teda je vo vyhrávajúcej pozícii. Ak sú na stole len dve rovnaké kartičky a nič iné, hráč na ťahu je v prehrávajúcej pozícii, lebo nech by spravil čokoľvek, protihráč sa dostane do výhernej pozície.

Z popisu vyššie môžeme vidieť, že pozícia, v ktorej je každá kartička v párnom počte, je prehrávajúca. Všetky ostatné – teda pozície, v ktorých je nejaká kartička v nepárnom počte – sú vyhrávajúce.

Riešenie

Potrebujeme zistiť, či je úvodná pozícia vyhrávajúca – teda či sa na vstupe nachádza aspoň jedno číslo nepárny počet krát. Existuje niekoľko spôsobov ako niečo takéto naprogramovať.

Jeden spôsob je, že si čísla zoradíme od najmenšieho po najväčšie, a budeme počítať, koľko rovnakých je za sebou. Takéto riešenie dostane plný počet bodov, existuje však o niečo krajšie riešenie:

Vyrobíme si dosť veľké pole a na \(i\)-tom políčku si budeme pamätať, koľko krát bolo na vstupe číslo \(i\). Takýto postup sa volá tiež Counting sort, ale môžeme si ho dovoliť len vtedy, keď sa nám dosť veľké pole zmestí do pamäte, teda keď rozsah čísel na kartičkách je dosť malý. Toto riešenie má časovú zložitosť \(O(n)\), pretože iba raz prejdeme naše vstupné pole. Pamäťová zložitosť je taktiež \(O(n)\), kde \(n\) je najväčšie možné číslo kartičky na vstupe.

n = int(input())
cards = [int(x) for x in input().split()]
counts = [0 for i in range(10**5 + 1)]

for c in cards:
  counts[c] += 1

for c in counts:
  if c % 2 == 1:
    print("Vlejd")
    exit(0)

print("John")

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> counts(100001,0);
    for(int i = 0; i < n; i++){
        int t;
        cin>>t;
        counts[t]++;
    }
    
    for(int i = 0; i <= 100000; i++){
        if(counts[i] % 2 == 1){
            cout << "Vlejd" << endl;
            return 0;
        }
    }
    cout << "John" << endl;
}

Je zaujímave uvedomiť si, že počet výskytov čísla si v skutočnosti nemusíme pamätať. Zaujíma nás iba, či sa dané číslo vyskytuje na vstupe párny alebo nepárny počet krát. Takúto hodnotu si môžeme uložiť ako \(True/False\) a keď príde nový výskyt daného čísla, iba hodnotu na pozícií tohoto čísla znegujeme – párny počet sa zmení na nepárny a naopak. Je dôležité si uvedomiť, že toto nám zmenší množstvo pamäte, ktorá bude použitá, ale asymptotická pamäťová zložitosť bude stále \(O(n)\), teda lineárna.

n = int(input())
cards = [int(a) for a in input().split()]
count = [False for i in range(100001)]

for c in cards:
  count[c] = not count[c]
    
for c in count:
  if c:
    print("Vlejd")
    exit(0)

print("John")