Zoznam úloh

1. Kobry sú plaché

Zadanie

Vedúci KSP boli na chate. Ako tak pripravovali nové zadania, poriadne im vyhladlo. Čakali, čakali a ešte dlhšie čakali, keď zrazu Dušan dostal geniálny nápad. Rozhodol sa, že si spolu s vedúcimi pôjdu ten obed uloviť. A tak vedúci išli do lesa s nádejou, že sa konečne budú môcť poriadne najesť.

V lese pobudli celkom dlhý čas, avšak nenašli nič, čo by sa dalo uloviť a zjesť. Po chvíli vyšli na lúku s vysokou trávou. Tam konečne zahliadli niečo, čo by si mohli uloviť. V tráve sa totiž hemžilo mnoho hadov rôznych dĺžok. A tak sa vedúci miesto lovenia si obedu pustili do hádania sa, kto z nich vidí hadov akej dĺžky. Pomôž vedúcim zistiť, aký je súčet dĺžok hadov v tráve, skôr, ako ich vedúci svojím krikom vyplašia.

Úloha

Na vstupe dostanete postupnosť rôznych znakov. Naším cieľom je spočítať súčet dĺžok všetkých hadov v tráve. Had sa skladá z hlavičky ~O dĺžky 1 (jazyk nepočítame), tela pozostávajúceho zo znakov =, pričom každý znak má dĺžku 1 (pozor, had môže mať aj telo dĺžky 0), a chvostíka > dlžky 1. Všetky hady sú orientované rovnakým smerom, a to takým, že vľavo sa nachádza hlavička a vpravo chvostík.

Formát vstupu

Vstup je reťazec dĺžky $N$.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
$1 \leq N \leq$ $500$ $10\,000$ $100\,000$ $10^6$

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, ktoré zobrazuje súčet dĺžky hadov.

Príklady

Vstup

~O==>~O>

Výstup

6

V tomto prípade sú v tráve $2$ hady, prvý má dĺžku $4$ a druhý $2$. Súčet ich dĺžok je teda $6$.

Vstup

~O===8>

Výstup

0

V tomto prípade v tráve nevidíme žiadne hady.

Na začiatok si musíme uvedomiť, že had pozostáva z hlavičky ~O, tela tvoreného znakom = a chvostíka >. Teda medzi hlavičkou a chvostíkom sa musia nachádzať iba znaky =, inak to nie je had. Taktiež vieme, že všetky hady sú orientované rovnakým smerom, a to takým, že hlavička je vždy naľavo od chvostíka.

Teda nám stačí prejsť reťazec z ľava do prava, a vždy, keď nájdeme hlavičku hada, pamätať si, že sme v tele hada a počítať jeho dĺžku, až kým nenarazíme na chvostík alebo iný znak. Ak nájdeme chvostík, stačí nám pripočítať dĺžku daného hada k celkovému súčtu dĺžok hadov, ak nájdeme iný znak, pokračujeme v hľadaní hlavičky.

Časová zložitosť

Časová zložitosť je $O(n)$, lebo prechádzame celým reťazcom iba raz.

Pamäťová zložitosť

Pamäťová zložitosť je $O(1)$, lebo si program pamätá iba niekoľko premenných - súčet dĺžok hadov a premennú, ktorá kontroluje, či sa práve nachádzame v hadovi alebo nie. Vzorový python kód má pamäťovú zložitosť $O(n)$, pretože načítava celý rad do pamäte. Vzorový C++ kód má pamäťovú zložitosť $O(1)$, pretože načítava iba jeden znak naraz. Na vyriešenie úlohy za plný počet bodov stačí implementácia s pamäťovou zložitosťou $O(n)$. 

hadik = input()
celkova_dlzka = 0
telo = 0
som_v_tele = False
for i in range(1,len(hadik)):
  if hadik[i-1] == "~" and hadik[i] == "O":
    telo = 1
    som_v_tele = True
  elif som_v_tele and hadik[i]=="=": 
    telo+=1
  elif som_v_tele and hadik[i]==">":
    celkova_dlzka += telo + 1
    telo = 0
    som_v_tele = False
  else:
    telo = -1
    som_v_tele = False
print(celkova_dlzka)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string input;
    cin >> input;

    int ans = 0;
    int cur = -1;

    for (char ch : input)
    {
        if (ch == '~')
            cur = 0;
        else if (cur == 0 && ch == 'O')
            cur = 1;
        else if (cur > 0 && ch == '=')
            cur++;
        else if (cur > 0 && ch == '>')
        {
            cur++;
            ans += cur;
            cur = -1;
        }
        else
            cur = -1;
    }

    cout << ans << '\n';
}
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty