Doprogramovanie do: 31. január 2022 23:59
11 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

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:

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

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.