Zadanie

Adam si chce pozrieť nový diel zo seriálu Mandalorian. Adam je fajnšmeker a chcel by si to pozrieť v najvyššej 4K kvalite, pre najlepší zážitok. Dokonca si kúpil aj novú televíziu, špeciálne kvôli tomuto seriálu (on Vám povie, že nie, ale neverte mu). Hodí sa do gauča, zapne Disney+ a pozerá sa. Nepozerá sa. Načítava sa.

Streamovať Mandalorian v 4K kvalite vyžaduje veľmi rýchly internet. Adam má dostatočne veľmi rýchly internet, ale nanešťastie, vo svojej sieti použil klasické, obojsmerné sieťové káble. Tieto káble sú ale zastarané a nie dosť rýchle na 4K kvalitu. Adamovi sa podarilo na populárnej stránke Krtkostarter™ nájsť nový druh sieťových káblov. Nové káble sú podľa ich vynálezcu, Krtka, kratšie, a teda rýchlejšie. Má to ale jeden háčik – káble fungujú iba v jednom smere. Toto ale Adam nemá problém vyriešiť a tak objednal pár zväzkov týchto káblov.

Po pár mesiacoch, troch oddialeniach prvej várky (nejaké výmysly o zamorení továrne hadmi šípkovitými – čo ešte nevymyslia) a zopár súdoch Adamovi prišiel balík s káblami. Ako to už ale býva s nakupovaním na Krtkostarter-i, nebolo to úplne to pravé orechové. Káble na sebe mali mať značenia, ktorým smerom vlastne fungujú. Po podrobnom preskúmaní si ale Adam všimol, že niektoré káble majú trochu divné označenie. Aby toho nebolo málo, niektoré káble sa začali hmýriť! Adam sa zvládne postarať o hmýriace sa hady, no musel Vás poprosiť o pomoc s triedením káblov. Pomôžte mu! (fakt si to už chce pozrieť!)

Úloha

Na každom kábli sa nachádza reťazec zložený zo šípok – znakov ‘<’ a ‘>’. Pokiaľ vynecháme všetky výskyty podreťazca susediacich “zátvorkových” šípok (reťazec <>), ostanú nám iba šípky, ktoré indikujú správny smer kábla. Na vstupe dostanete vždy jeden kábel a Vašou úlohou bude povedať, či je kábel ľavo-dátový alebo pravo-dátový.

Formát vstupu

Na vstupe sa nachádza práve jeden riadok – reťazec znakov ‘<’ a ‘>’ – náš kábel. Každý vstup má zaručené, že sa skladá iba z reťazcov <> a zvyšných znakov, ktoré budú vždy iba šípky smerujúce jedným smerom, doľava (‘<’) alebo doprava (‘>’). Adam kupoval iba kratšie káble, teda dĺžka reťazca \(n\) nepresiahne \(10^6\) znakov.

Formát výstupu

Na výstup vypíšte práve jeden riadok s jedným z nasledujúcich reťazcov – lavo-datovy pokiaľ je kábel ľavo-dátový, teda všetky jeho šípky, ktoré nepatria k šípkovým zátvorkám <>, mieria doľava. Nápodobne vypíšte reťazec pravo-datovy, pokiaľ je kábel pravo-dátový, teda všetky jeho nezátvorkové šípky ukazujú doprava.

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledujúce obmedzenia:

Sada 1–2 3–4 5–8
\(1 \leq n \leq\) \(100\) \(1\,000\) \(1\,000\,000\)

Príklad

Input:

<

Output:

lavo-datovy

V prvom príklade má kábel iba jednu ľavú šípku a teda musí byť ľavo-dátový.

Input:

<><><>><><>>><>><>

Output:

pravo-datovy

Druhý prípad je už trochu zamotanejší, no môžeme si všimnúť, že po troch pároch šípok narazíme na samotnú šípku smerom doprava. Vo zvyšku reťazca narazíme na ďaľšie osamelé šípky pravým smerom, no žiadnu osamelú smerom doľava, teda kábel musí byť pravo-dátový.

Jedno riešenie

Máme teda naše káble, v celej ich jednosmernej kráse. Podľa zadania sa v nich nachádzajú iba znaky < alebo > (kvačky), a reťazce <> (3D dlaždice). Vedeli by sme spraviť to, že načítame celý vstup, prečístíme ho od <> reťazcov a zbytok, čo nám ostane, budú kvačky indikujúce správny smer. Stačí sa teda len na jednu z nich pozrieť a prehlásiť, ktorým smerom mieri. Toto riešenie nie je ale úplne efektívne, a to hlavne preto, že si musíme zapamätať všetky znaky zo vstupu, čo je \(O(n)\) – lineárna pamätová zložitosť. Časová zložitosť je ale taktiež lineárna – \(O(n)\) – pretože iba vstup načítame, a zopár krát ho prejdeme. To je dobré, pretože aj tak potrebujeme lineárny čas už len na to, aby sme vstup načítali. Ak ste sa ešte neučili používať polia alebo reťazce (stringy), napísanie tohoto riešenia je skvelé cvičenie na oboznámenie sa ;)

Lepšie riešenie

Prirodzene prichádza otázka, dá sa to lepšie? Áno, dá. Skúsme sa pozrieť na počty kvačiek, konkrétne ľavých a pravých. Majme dve premenné, v ktorých si budeme ukladať počet ľavých a pravých kvačiek, ktoré sme videli. Môžeme si všimnúť, že pokiaľ sa v reťazci nachádza <>, pripočíta sa nám ľavá aj pravá kvačka. Pokiaľ sa ale v reťazci nachádza iba ľavá alebo pravá, pripočíta sa nám iba príslušná premenná. Čo to znamená? Predstavme si, že sa v reťazci nenachádzajú reťazce <>. Ako tento reťazec vyzerá? Chvíľka napätia! Vyzerá nejako takto <<<<<<<<, takto >>>>>>>>>>>, alebo taaaaktoooo <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<.

Pokiaľ sa vrátime k našemu počítaniu kvačiek, uvedomíme si, že po spočítaní nám ostane v jednej premennej viac započítaných kvačiek, ako v druhej. A to je naše riešenie. Spočítame ľavé/pravé kvačky, porovnáme, kde je ich viac a vyhlásime smer káblu. Toto riešenie má lepšiu pamäťovú zložitosť, konštantnú, teda \(O(1)\). To znamená, že máme fixne pre akokoľvek veľký vstup iba dve premenné.1

#include <iostream>

using namespace std;

int main() {
    int pocet_lavych_kvaciek = 0,
        pocet_pravych_kvaciek = 0;
    char kvacka;
    while (cin >> kvacka) {
        if (kvacka == '<') {
            pocet_lavych_kvaciek++;
        } else {
            pocet_pravych_kvaciek++;
        }
    }
    if (pocet_pravych_kvaciek < pocet_lavych_kvaciek) {
        cout << "lavo-datovy" << endl;
    } else  {
        cout << "pravo-datovy" << endl;
    }
    return 0;
}
#/usr/bin/env python3

kabel = input()

pocet_lavych_kvaciek = 0
pocet_pravych_kvaciek = 0
for sipka in kabel:
    if sipka == '<':
        pocet_lavych_kvaciek += 1
    elif sipka == '>':
        pocet_pravych_kvaciek += 1

if pocet_lavych_kvaciek < pocet_pravych_kvaciek:
    print("pravo-datovy")
elif pocet_lavych_kvaciek > pocet_pravych_kvaciek:
    print("lavo-datovy")

  1. Aj napriek tomuto má vzorové riešenie v Pythone pamäťovú zložitosť \(O(n)\), pretože načítava celý vstup naraz. Načítavanie znak po znaku je totiž v Pythone trochu nepraktické.↩︎

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