Zadanie

Baklažán a Buj sa hrajú hru. Zoberú balíček kariet a rozdelia ho na kôpky. Každá karta má na sebe napísané číslo predstavujúce body. Potom striedavo ťahajú z kôpok, pričom hráč na ťahu si vždy zvolí z ktorej kôpky odoberie kartu. Aby to nebolo príliš zložité, tak sa dohodli, že Baklažán bude brať kartu iba z vrchu a Buj iba zo spodu. Hra sa končí vtedy, keď sa minú karty a vyhráva ten s najväčším súčtom bodov.
Obaja majú ale veľa povinnosti v škole. Chceli by vás teda poprosiť aby ste zopár hier odohrali za nich. Odkazujú, že by obaja hrali optimálne.

Úloha

Zistite koľko bodov bude mať Baklažán a Buj po skončení hry ak obaja budú hrať optimálne. Hru vždy začína Baklažán.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) \((1 \leq n \leq 100)\), počet kôpok kariet. Za ním nasleduje \(n\) riadkov. V každom nasledujúcom riadku je číslo \(s_{i}\) \((1 \leq s_{i} \leq 100)\) označujúce počet kariet v \(i\)-tej kôpke. Za ním nasleduje \(s_{i}\) čísel \(c_{1}, c_{2}, ..., c_{s_{i}}\), hodnoty kariet od vrchu kôpky až po spodok. Pre ľubovolné \(c_{k}\) platí, \((1 \leq c_{k} \leq 1000)\).

Čiastočné body môžete získať v sade 1, kde je vždy počet kôpok rovný \(1\). Pre sadu 2 platí, že počet kôpok je \(2\).

Formát výstupu

Na výstup vypíšte dve čísla. Počet bodov Baklažána a počet bodov Buja po ukončení hry.

Príklady

Input:

2
1 100
2 1 10

Output:

101 10

Baklažán si zobral katru 100, Buj 10 a nakoniec Baklažán 1.

Input:

1
9 2 8 6 5 9 4 7 1 3

Output:

30 15

Baklažán by si zobral karty 2, 8, 6, 5, 9 a Buj 3, 1, 7, 4.

Input:

3
3 1 3 2
2 8 7
3 5 4 6

Output:

18 18

Hra by mohla prebiehať napríklad takto:
Baklažán zoberie kartu z tretej kôpky (skóre 5:0)
Bui zoberie kartu z druhej kôpky (skóre 5:7)
Baklažán zoberie kartu z druhej kôpky (skóre 13:7)
Bui zoberie kartu z tretej kôpky (skóre 13:13)
Baklažán zoberie kartu z tretej kôpky (skóre 17:15)
Bui zoberie kartu z prvej kôpky (skóre 17:15)
Baklažán zoberie kartu z prvej kôpky (skóre 18:15)
Bui zoberie kartu z prvej kôpky (skóre 18:18)

Prvá sada (jedna kôpka)

Na riešenie prvej sady, kde bola iba jedna kôpka, stačilo striedavo simulovať Baklažánove a Bujove ťahy. Takéto riešenie pobehá v lineárnom čase (neskôr ukážeme, že vieme mať dokonca konštantnú pamäť).

Riešenie pre viacero kôpok

Tu je situácia podstatne ťažšia. Je veľmi veľa možností ako vie hra prebiehať a nestíhame preskúšať každú. Prvá vec, čo si treba uvedomiť je, že sa nestačí pozerať len na prvú/poslednú kartu na kôpke. Takáto karta môže mať veľmi malú hodnotu, ale môže odkryť karty, ktoré sa veľmi oplatia zobrať.

Ďalšia vec, ktorú si vieme všimnúť je, že porebujeme rozlišovať medzi 2 typmi kôpok – párnymi a nepárnymi. Zamyslime sa nad párnymi kôpkami.

Kôpky s párnym počtom kariet

Ako tu vyzerá optimálna hra? Všimnime si, že žiaden hráč nemôže získať kartu, ktorá je vo vzdialenejšej polke kôpky. Prečo?

  1. Bujovi stačí ťahať z tej istej kôpky, z ktorej bral Baklažán.
  2. Baklažánova stratégia je podobná. Ak Buj potiahne kartu z inej kôpky ako on, Baklažán sa prispôsobí a zoberie z tej kôpky, čo Buj.

Čo sme týmto zistili? Predstavme si, že existuje optimálne riešenie pre jedného z hráčov, s tým, že v nejakom momente zoberie kartu zo vzdialenej polky kôpky. My sme ale dokázali, že obaja hráči vedia takémuto prípadu zabrániť. To znamená, že v optimálnom riešení Baklažán získa vrchnú polku kôpky a Buj spodnú.

Kôpky s nepárnym počtom kariet

Teraz sa pozrime na nepárne kôpky. Zjavne aj tu platí tá istá stratégia, akurát, čo s kartou v prostriedku kôpky? Keď popremýšľame, vieme ukázať, že Buj nevie zabrániť Baklažánovi získať najlepšiu strednú kartu spomedzi nepárnych kôpok. Podobne, ak Baklažán túto kartu zoberie, nevie zabrániť Bujovi zobrať druhú najdrahšiu. A toto vieme zovšeobecniť – Baklažán a Buj si postupne poberú karty v nepárnych kôpkach.

Celé riešenie dokopy

Na začiatku načítame vstup, pripočítame Baklažánovi skóre za vrchné polky kôpok, Bujovi za spodné. Potom, zoberieme prostredné karty v nepárnych kôpkach, utriedime ich a striedavo rozdelíme medzi Baklažána a Buja. Časová zložitosť takéhoto riešenia je \(O(n \cdot s + n \cdot \log(n))\), pamäťová \(O(n \cdot s)\), kde \(n\) je počet kôpok a \(s\) je maximálny počet kariet v kôpke.

Ide to aj rýchlejšie a úspornejšie

V skutočnosti si vôbec nemusíme pamätať všetky kôpky. Stačí, keď ich budeme spracuvávať jednu po druhej. Párnu rovno spracujeme a z nepárnych si uložíme prostredný prvok. Tie na konci usporiadame a rozdelíme chalanom. Týmto sme zlepšili pamäťovú zložitosť z \(O(n \cdot s)\) na \(O(n + s)\) lebo máme \(s\) kariet v kôpke a môžeme dostať \(n\) nepárnych kôp.

Časovú zložitosť vieme zlepšiť usporiadaním prostredných kariet pomocou counting sortu, keďže hodnoty jednotlivých kariet sú do \(1000\). Pretože counting sort triedi v linárnom čase od počtu triedených prvkov, teda v \(O(n)\), výsledná časová zložitosť bude \(O(n \cdot s)\). Prípadne vieme spraviť tesnejší odhad – zložitosť bude lineárna od počtu všetkých kariet na vstupe. Keďže musíme vždy prečítať celý vstup, takéto riešenie má dokonca najlepšiu možnú asymptotickú zložitosť spomedzi všetkých programov riešiacich túto úlohu.

Ešte jedna finta nakoniec. Vďaka tomu, že vieme koľko kariet má každá kôpka, kôpky si nemusíme pamatať. Vieme ich spracovať postupne po kartách a pamätať si len Bujove a Baklažánove skóre. Pamäťová zložitosť bude potom \(O(n)\).

#!/usr/bin/env python3

odd, even = [], []
player1_turn = True
player1 = player2 = 0
pile_number = int(input())

for _ in range(pile_number):
    n, *pile = tuple(map(int, input().split()))
    if n % 2 == 0:
        even.append(pile)
    else:
        odd.append(pile)

for pile in even:
    n = len(pile)
    player1 += sum(pile[:n//2])
    player2 += sum(pile[n//2:])

for pile in sorted(odd, reverse=True, key=lambda x: x[len(x)//2]):
    n = len(pile)
    top, middle, bottom = pile[:n//2], pile[n//2], pile[n//2+1:]
    player1 += sum(top)
    player2 += sum(bottom)
    if player1_turn:
        player1 += middle
        player1_turn = not player1_turn
    else:
        player2 += middle
        player1_turn = not player1_turn

print(player1, player2)

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