Zadanie

Paulínka žije v meste, ktoré si vieme predstaviť ako nekonečnú štvorčekovú sieť. Na serveri Firmy Komerčných Softvérov našla tajný prototyp novej revolučnej aplikácie, ktorá dokáže nájsť trasu do ľubovoľného miesta v tomto meste v konštantnom čase. Hneď ju išla vyskúšať a vytlačila si trasu do nového obchodného centra v meste. Ako vychádzala zo svojho domu, vytlačené inštrukcie sa jej v daždi premočili. Z pôvodne vytlačených šípok zostali len vertikálne a horizontálne čiary. Kam najďalej od pôvodného cieľa sa môže Paulínka dostať?

Úloha

Paulínka mala zoznam šípok (<, >, ^ a v), z ktorých sa jej stratila informácia o ich smere. Teraz vie iba, či boli šípky vertikálne alebo horizontálne. Na svojej ceste sa Paulínka vždy musí rozhodnúť, či pôjde doľava/doprava, ak má napísanú horizontálnu čiarku, resp. hore/dole, ak má napísanú vertikálnu čiarku. Paulínka býva v bode \((0, 0)\) štvorčekovej siete. Zistite, ako by musela vyzerať Paulínkina cesta, keby sa čo najviac stratila (teda skončila by čo najďalej od pôvodného cieľa cesty).

Formát vstupu

Na vstupe sa nachádza jeden reťazec dĺžky \(n\) – výpis pôvodnej cesty, zložený zo znakov <, >, ^ a v.

Formát výstupu

Na výstup napíšte jeden riadok dĺžky n – výpis cesty, zložený zo znakov <, >, ^ a v, ktorú by Paulínka musela prejsť, aby skončila čo najďalej od pôvodného cieľa (Euklidovská vzdialenosť).

Hodnotenie

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(100\) \(1\,000\) \(10\,000\) \(1\,000\,000\)

Príklad

Input:

>>^

Output:

<<v

Input:

v<<vvv<vv<<<

Output:

^>>^^^>^^>>>

Myšlienka riešenia

Na to, aby sme vedeli vytvoriť cestu, ktorá bude viesť čo najďalej od tej pôvodnej, musíme najprv zistiť, kde končí cesta na vstupe. Prečítame vstup a pre každý znak posunieme Paulínku na štvorčekovej sieti. Paulínka začína v bode \((0, 0)\). Ak na vstupe máme >, pripočítame k jej x-ovej súradnici \(1\), ak <, jednotku odčítame. Podobne to bude fungovať aj s ^ a v. Po prečítaní celého vstupu vieme súradnice bodu, v ktorom Paulínka mala skončiť.

Teraz sa na vstup pozrieme ešte raz a budeme vymieňať šípky tak, že všetky šípky, ktoré sú orientované smerkom k cieľu vymeníme za opačné. Teda, ak na vstupe máme šípku < a cieľ je naľavo od \((0, 0)\), vymeníme ju za >. Keby bol cieľ napravo, šípku necháme tak, ako bola.

Časová a pamäťová zložitosť

Keďže sa iba niekoľkokrát pozrieme na celý vstup, časová zložitosť bude lineárne závislá od dĺžky vstupu – \(O(n)\).

Pamäťová zložitosť bude tiež \(O(n)\), keďže si musíme pamätať celý vstup a konštantný počet premenných – súradnice pôvodného cieľa.

arrows = input()
position_x = 0
position_y = 0

for arrow in arrows:
    if arrow == "<":
        position_x -= 1
    if arrow == ">":
        position_x += 1
    if arrow == "^":
        position_y += 1
    if arrow == "v":
        position_y -= 1

for arrow in arrows:
    if arrow == "v" or arrow == "^":
        if position_y > 0:
            print("v", end="")
        else:
            print("^", end="")
    else:
        if position_x > 0:
            print("<", end="")
        else:
            print(">", end="")

print()  # newline na konci

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