Zadanie

MisQo sa veľmi rád pozerá na hru Subway Surfers. Tak si raz povedal, že si ju skúsi naprogramovať. Keďže nie je moc dobrý programátor, rozhodol sa hru nasledovne zjednodušiť. Keďže má veľmi rád mačky, rozhodol sa, že hráč bude myš a mačka ju bude naháňať, bude sa mu na to potom ešte lepšie pozerať.

Úloha

MisQova verzia Subway Surfers pozostáva z 2 vertikálnych línii, na ktorých sa dá hýbať. Podobne ako v originálnej hre tu musíme preskakovať prekážky. Tu ale hráme za myš a naháňa nás agresívna mačka. Myš môže robiť iba nasledovné 3 akcie:

  • posunúť sa o 1 dopredu.
  • posunúť sa o 1 dozadu.
  • skočiť - zmení sa línia v ktorej sa myš nachádza a zároveň sa posunie o \(k\) dopredu.

Po každom pohybe hráča sa mačka posunie o 1 dopredu. Ak nastane situácia, že sa myš a mačka nachádzajú na rovnakej vzdialenosti od začiatku (Mačka je veľká, teda zaberá obe línie naraz), prípadne mačka predbehne myš, mačka myš zje a tým pádom myš prehrala.

Na rozdiel od originálnej hry, táto verzia má koniec, keď sa dostaneš na koniec levelu. Rozhodni, či pre dané prekážky sa dá level vyhrať. To znamená, že sa dá dostať aspoň na koniec levelu bez toho, aby ťa mačka zjedla. (koniec vieme aj preskočiť - ak má level 15 políčok a my skočíme rovno na 18., tak sme vyhrali).

Na začiatku hry sa myš nachádza na 1. pozícii v 1. línii a mačka na 0. pozícii tesne za ňou. Je garantované, že na tejto pozícii nie je prekážka.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) – dĺžka levelu, a číslo \(k\) (\(1 \leq k \leq n\)) – dĺžka myšieho kroku.

V druhom riadku je \(n\) znakov - mapa prvej línie hry, kde znak X značí prekážku a znak = značí voľno. V treťom riadku je znova \(n\) znakov - mapa druhej línie hry, kde znak X značí prekážku a znak = značí voľno.

Úloha má osem sád vstupov, v ktorých platia nasledovné obmedzenia:

Sada 1, 2 3, 4 5, 6 7, 8
\(1 \leq n \leq\) \(20\) \(100\) \(1\,000\) \(10^5\)

Formát výstupu

Vypíš jeden riadok a v ňom Vyhral som, ak sa dá level vyhrať, inak Prehral som.

Príklady

Input:

8 4
==XX=XX=
==X==X==

Output:

Vyhral som

Myši stačí iba 2-krát skočiť - po prvom skoku budeme na 5-tom políčku v druhej línii, odkiaľ už vieme rovno skočiť do cieľa. Rovnako by sme mohli po prvom skoku ísť dozadu a potom skočiť

Input:

8 3
=X=XXXX=
=X==XX==

Output:

Prehral som

Ako prvý krok musí myš skočiť, lebo hneď pred nami je prekážka. Po skoku sa dostaneme na 4. políčko v druhej línii. Jediný možný ťah je ísť dozadu. Potom jediný možný ťah je ísť naspäť dopredu. Takto sa budeme cykliť až kým nás mačka nechytí, teda prehráme.

Pozrime sa na to, ako sa dá popísať stav hry. To vieme pomocou troch hodnôt - naša pozícia, v ktorej línii sa nachádzame a to, že ako ďaleko je mačka. Označme si tento stav ako trojicu (p, l, m) - . Povedzme teraz, že máme takýto stav a pozrime sa na to, do akých stavov sa môžeme dostať na jeden krok. Máme teda 3 možnosti: - Ak sa posunieme dopredu, tak naša pozícia sa zväčší o 1 a mačka sa tiež posunie o 1. Nový stav bude (p+1, l, m+1). - Ak sa posunieme dozadu, tak naša pozícia sa zmenší o 1 a mačka sa tiež posunie o 1. Nový stav bude (p-1, l, m+1). - Ak skočíme, tak sa pohneme o k krokov dopredu a zmeníme líniu. Nový stav bude (p+k, !l, m+1).

Na začiatku sme v stave (1, 0, 0). Víťazný stav je hocičo, ktore má p vačšie ako n.

Bruteforce

Ako prvé čo nás napadne je skúšať všetky možné ťahy. Teda začneme počiatočným stavom a rekurzívne sa zavoláme pre všetky stavy do ktorých sme sa vedeli dostať na jeden krok a zároveň musí platiť, že mačka nás nezožerie (m < p) a taktiež nemôžeme skončiť na prekážke, teda políčko na ktorom skončíme musí byť prázdne. Tým, že mačka sa dostane na koniec levelu, tak toto riešenie musí skončiť.

Po každom našom pohybe sa mačka pohne o políčko hore, takže ak neutečieme o \(n\) krokov, neutečieme vôbec. Takže skúšame najviac každú postupnosť \(n\) možných ťahov, a v každom momente máme navýber najviac \(3\) možné ťahy. Teda takéto riešenie vyskúša nanajvýš \(3^n\) postupností ťahov.

Optimálne riešenie

Všimnime si, že predošlé riešenie skúša nejaké stavy zbytočne viackrát. Napríklad, ak k=1, tak do stavu (3,0,2) sa vieme dostať dvoma spôsobmi - dvakrát ideme dopredu, alebo dvakrát skáčeme. Potom z tohto stavu by sme ďalej skušali všetky stavy odtiaľto zbytočne 2-krát. Čiže si potrebujeme sledovať, že v akých stavoch sme už boli, aby sme ich neriešili viackrát. To vieme docieliť napríklad pomocou slovníka v pythone.

Pozrime sa ďalej na príklad, že sa nejakú pozíciu vieme dostať dvoma rôznymi spôsobmi, pričom v jednom je mačka ďalej od nás. Zjavne ak vieme uniknúť v neskoršom čase, tak to zvládneme aj keby sme unikli skôr. Naopak ak si vyberieme tú dlhšiu cestu, tak sa to neskôr môže pokaziť a mačka nás chytí. Teda vieme povedať, že ak to pôjde, tak to nutne pôjde tou najkratšou cestou. Na vyriešenie tohto problému vieme použiť klasické prehľadávanie do šírky.

Namiesto rekurzie máme frontu v ktorej si uchovávame stavy do ktorých sme sa nejak dostali. Na začiatku do nej pridáme počiatočný stav a potom opakujeme kým sa fronta nevyprázdni, alebo sme sa dostali do cieľa. Pri každej iterácii si z fronty vyberieme prvý stav, označíme si, že sme v tomto stave už boli a potom z neho skúsime spraviť všetky 3 ťahy a stavy do ktorých sme sa dostali pridáme do fronty. Pridávame samozrejme iba povolené ťahy, také pri ktorých neskončíme na prekážke a ani nás mačka nezožerie.

Pozrime sa na časovú a pamäťovú zložitosť tohto riešenia. Tým, že na každé políčko sa pozeráme iba raz, tak časová zložitosť bude lineárna od počtu políčok, teda celkovo to bude \(O(n)\). Potrebujeme si pamätať, na ktorom políčku sme už boli, aby sme žiadne políčko nenavštívili viackrát. Teda pamäťová zložitosť bude taktiež \(O(n)\).

n, k = map(int, input().split())
first = input()
second = input()
first_visited = [False for x in range(n)]
second_visited = [False for s in range(n)]

q = []
q.append((0,0,0))
ans = False

while len(q) > 0:
  curr = q.pop(0)
  if curr[0] >= n:
    ans = True
    break

  if curr[2] >= curr[0]:
    continue
  if curr[1] == 1 and second_visited[curr[0]]:
    continue
  if curr[1] == 0 and first_visited[curr[0]]:
    continue

  if curr[1] == 0:
    first_visited[curr[0]] = True
    if curr[0] - 1 > 0 and first[curr[0] - 1] != 'X':
      if curr[0] - 1 > curr[2]:
        q.append((curr[0] - 1, 0, curr[2] + 1))
    if curr[0] + 1 >= n or first[curr[0] + 1] != 'X':
      q.append((curr[0] + 1, 0, curr[2] + 1))
    if curr[0] + k >= n or second[curr[0] + k] != 'X':
      q.append((curr[0] + k, 1, curr[2] + 1))
  elif curr[1] == 1:
    second_visited[curr[0]] = True
    if curr[0] - 1 > 0 and second[curr[0] - 1] != 'X':
      if curr[0] - 1 > curr[2]:
        q.append((curr[0] - 1, 1, curr[2] + 1))
    if curr[0] + 1 >= n or second[curr[0] + 1] != 'X':
      q.append((curr[0] + 1, 1, curr[2] + 1))
    if curr[0] + k >= n or first[curr[0] + k] != 'X':
      q.append((curr[0] + k, 0, curr[2] + 1))

if ans:
  print('Vyhral som')
else:
  print('Prehral som')
#include <bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;

struct Stav {
  int macka;
  int linia;
  int pozicia;
};

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, k;
  cin >> n >> k;
  vector<char> prva_linia(n), druha_linia(n);
  vector<char> first_visited(n, 0), second_visited(n, 0);
  for (int i = 0; i < n; i++) {
    cin >> prva_linia[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> druha_linia[i];
  }

  queue<Stav> q;
  q.push({0, 0, 0});
  bool odpoved = false;

  while (!q.empty()) {
    Stav terajsi_stav = q.front();
    q.pop();

    if (terajsi_stav.pozicia >= n) {
      odpoved = true;
      break;
    }

    if (terajsi_stav.macka > terajsi_stav.pozicia) {
      continue;
    }
    if (terajsi_stav.linia == 1 && second_visited[terajsi_stav.pozicia]) {
      continue;
    }
    if (terajsi_stav.linia == 0 && first_visited[terajsi_stav.pozicia]) {
      continue;
    }

    Stav nasledujuci;
    nasledujuci.macka = terajsi_stav.macka + 1;
    nasledujuci.linia = terajsi_stav.linia;

    if (terajsi_stav.linia == 0) {
      first_visited[terajsi_stav.pozicia] = 1;
      if (terajsi_stav.pozicia - 1 > 0 && prva_linia[terajsi_stav.pozicia - 1] != 'X') {
        nasledujuci.pozicia = terajsi_stav.pozicia - 1;
        if (nasledujuci.pozicia >= nasledujuci.macka) {
          q.push(nasledujuci);
        }
      }

      if (prva_linia[terajsi_stav.pozicia + 1] != 'X') {
        nasledujuci.pozicia = terajsi_stav.pozicia + 1;
        q.push(nasledujuci);
      }

      if (terajsi_stav.pozicia + k >= n || druha_linia[terajsi_stav.pozicia + k] != 'X') {
        nasledujuci.pozicia = terajsi_stav.pozicia + k;
        nasledujuci.linia = 1;
        q.push(nasledujuci);
      }
    } else if (terajsi_stav.linia == 1) {
      second_visited[terajsi_stav.pozicia] = 1;
      if (terajsi_stav.pozicia - 1 > 0 && druha_linia[terajsi_stav.pozicia - 1] != 'X') {
        nasledujuci.pozicia = terajsi_stav.pozicia - 1;
        if (nasledujuci.pozicia > nasledujuci.macka){
          q.push(nasledujuci);
        }
      }

      if (terajsi_stav.pozicia + 1 >= n || druha_linia[terajsi_stav.pozicia + 1] != 'X') {
        nasledujuci.pozicia = terajsi_stav.pozicia + 1;
        q.push(nasledujuci);
      }

      if (terajsi_stav.pozicia + k >= n || prva_linia[terajsi_stav.pozicia + k] != 'X') {
        nasledujuci.pozicia = terajsi_stav.pozicia + k;
        nasledujuci.linia = 0;
        q.push(nasledujuci);
      }
    }
  }

  if (odpoved) {
    cout << "Vyhral som" << '\n';
  } else {
    cout << "Prehral som" << '\n';
  }
}

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