2. Raz sa stratiť musím (vzorové riešenie)

Zadanie

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Stankovi na email [email protected]

Cez zimu sa veľmi oteplilo, a tak sa Hanka rozhodla, že sa pôjde prejsť po Petržalke. Hanka má však obrovský talent, takzvaný “orientačný nezmysel”. To znamená, že sa dokáže stratiť aj na miestach, kde by si si povedal/a, že to je nemožné. Keďže o tejto svojej schopnosti vedela, tak si zobrala kompas a na každej križovatke si zapísala ktorým smerom išla daľej. Keďže ale budovy aj križovatky v Petržalke sú všetky na prvý pohľad rovnaké, tak sa hneď stratila a odbočila preč od svojej plánovanej cesty. Preto jej teda musíte pomôcť zistiť kde je, aby potom nejako trafila naspäť domov.

Úloha

Tvojou úlohou je zistiť Hankinu výslednú pozíciu z toho, ktorými smermi odbočovala. Mapu Petržalky si vieme predstaviť ako dokonalú štvorčekovú sieť s \(r\) riadkami a \(s\) stĺpcami, kde križovatky sú mrežové body. Hanka začína na križovatke so súradnicami \(p_y\), \(p_x\). Ďalej platí, že okolo mesta nič nie je, takže vždy ak Hanka zistila, že odbočila mimo mesta¹, tak sa otočila a vrátila na predchádzajúcu križovatku v meste, kde bola predtým.

Formát vstupu

Na prvom riadku vstupu dostanete 3 medzerou oddelené čísla \(r\), \(s\), \(n\) – označujúce počet riadkov mapy (výšku mapy), stĺpcov mapy (šírku mapy) a dĺžku Hankinej cesty. Platí, že \(1 \leq r, s \leq 10^9\), \(1 \leq n \leq 10^6\).
Na druhom riadku je dvojica čísel \(p_y\), \(p_x\) – Hankina počiatočná pozícia. Prvé číslo označuje riadok a druhé stĺpec na mape, kde sa Hanka na začiatku nachádzala.
Platí, že \(0 \leq x \leq s\), \(0 \leq y \leq r\). Na treťom riadku je opis samotnej cesty – reťazec znakov SJVZ. Znaky v ceste nie sú oddelené medzerou.

Riadky siete číslujeme od nuly, od vrchu mapy. Stĺpce číslujeme tiež od nuly z ľavej strany mapy

Je 5 sád vstupov, za každú správne vyriešenú máš 20 bodov. Pre jednotlivé sady platia nasledovné obmedzenia:

Sada	1	2	3	4	5
\(1 \leq n \leq\)	\(10\)	\(1000\)	\(1000\)	\(10^6\)	\(10^6\)
\(1 \leq r,s \leq\)	\(10\)	\(1000\)	\(10^6\)	\(10^6\)	\(10^9\)

Formát výstupu

Na výstup vypíš Hankinu výslednú pozíciu ako dve medzerou oddelené čísla. Najprv vypíš y-ovú súradnicu a potom x-ovú.

Príklad

Input:

4 5 10
1 2
JVJZZSSVVV

Output:

1 4

Hanka sa v tomto prípade pohybovala takto:

Input:

4 5 7
1 0
VSSVJJV

Output:

2 3

Hanka sa teraz sa hýbala takto. Všimnite si, že po druhom kroku išla hore, nakoľko ale odišla von z mesta, musela sa vrátiť naspäť.

Toto zistiť zvláda, nakoľko zrazu okolo nej prestanú byť paneláky, alebo sa ocitne v strede Dunaja↩︎

Predstavme si, že túto úlohu chceme vyriešiť sami bez programovania. Asi ako prvé nás napadne si zobrať štvorčekový papier a kresliť si cestu podľa inštrukcii zo vstupu. Potom sa pozrieme, že kde sme skončili.

Presne toto isté chceme naprogramovať. Budeme používať dve premenné \(x\) a \(y\) v ktorých máme našu aktuálnu pozíciu. Jednotlivé smery s nimi budú robiť toto:

S - \(y\)-ová súradnica sa o 1 zmenší
J - \(y\)-ová súradnica sa o 1 zväčší
V - \(x\)-ová súradnica sa o 1 zväčší
Z - \(x\)-ová súradnica sa o 1 zmenší

Hýbať sa vieme, takže už stačí len zabezpečiť to, že nikdy nevylezieme von z mapy. Naša mapa má vždy fixné rozmery - \(r\) riadkov a \(s\) stĺpcov. Takže \(x\) musí byť vždy v rozsahu od 0 po \(r\). To isté vieme povedať o \(y\). Na ošetrenie vychádzania z mapy budeme musieť obe premenné držať v tom rozsahu, čiže ak vyjdu von, tak ich musíme vrátiť naspäť. Program bude celkovo vyzerať napríklad takto:

stlpce, riadky, n = map(int, input().split())
y, x = map(int, input().split())
cesta = input()

for krok in cesta:
    if krok == 'S':
        y -= 1
    elif krok == 'J':
        y += 1
    elif krok == 'Z':
        x -= 1
    elif krok == 'V':
        x += 1
        
    if x < 0:
        x = 0
    if x > riadky:
        x = riadky
    if y < 0:
        y = 0
    if y > stlpce:
        y = stlpce

print('{y} {x}'.format(y=y, x=x))

Čas, ktorý nám program bude bežať rastie lineárne od veľkosti vstupu, takže vieme povedať, že naše riešenie bude mať lineárnu časovú zložitosť. Veľkosť pamäte, ktorú potrebujeme sa nám nijak nemení od veľkosti vstupu, dokonca si nemusíme ani pamätať samotný vstup. Pamätová zložitosť bude teda konštantná

Krajšie riešenie

Riešenie vyššie fungovalo optimálne, ale pomocou rôznych trikov vieme náš program o dosť skrátiť (nie časovo ani pamäťovo, ale počtom riadkov kódu). Keď sa pozrieme na vyhodnocovanie krokov, tak sme tam predtým mali 4 podmienky a každý smer sme riešili zvlášť. Namiesto toho si vieme vytvoriť 2 slovníky¹ \(dx\) a \(dy\), v ktorých budeme mať pre každý smer uložené ako sa po ňom zmenia naše súradnice. Ďalší trik ktorý sa tu dal využiť sú funkcie \(min\) a \(max\) (obe dostávajú ako parametre 2 čísla a vrátia minimum / maximum z nich), ktorými vieme vylepšiť vyliezanie z mapy. Konkrétne \(x = min(0, max(r, x))\) nám spraví, že x nikdy nevyjde z intervalu \(<0,r>\). Skús sa zamyslieť prečo to tak funguje.

r, s, n = map(int, input().split())
y, x = map(int,input().split())
cesta = input()

dx = { 'S':  0, 'J': 0, 'V': 1, 'Z': -1 }
dy = { 'S': -1, 'J': 1, 'V': 0, 'Z':  0 }

for c in cesta:
    x = min(s, max(0, x + dx[c]))
    y = min(r, max(0, y + dy[c]))

print(y,x)

slovník si vieme predstaviť ako pole, ktoré môže mať ako indexy nielen čísla, ale aj reťazce, alebo hocičo iné↩︎

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

2. Raz sa stratiť musím vzorové riešenie