Zadanie

Malý Marcelko je introvert, a tak si v škôlke spestruje dni tým, že len veľmi z diaľky pozoruje svojich spolužiakov, keď si kreslia voskovkami. Keďže sa zatiaľ naučil počítať iba do \(4\), pozoruje, čo sa deje počas kreslenia s týmito \(4\) druhmi voskoviek – guľatou, kučeravou, špicatou a hranatou (voskovky si môžeme predstaviť ako príslušné zátvorky). Jeho novou zábavkou je písať si na papier záznamy o tom, čo sa deje s ktorou voskovkou. Na papier napíše otváraciu – ľavú zátvorku (príslušného typu), keď si nejaký spolužiak danú voskovku vezme zo stolíka. Naopak, keď ju položí na stolík, zapíše si zatváraciu – pravú zátvorku (príslušného typu). Na začiatku a na konci dňa sa všetky voskovky nachádzajú na stole. Občas sa ale Marcel zadíva na Sabinku a zabudne zapisovať niektoré zobratia alebo položenia voskoviek, alebo zapíše nejaké zobratia a položenia zle. Potom mu vznikajú všelijaké čudné zápisy a je smutný, lebo si nie je istý, či niečo nezmeškal. Pomôžte mu overiť, či jeho zápis mohol vzniknúť zapisovaním pohybov voskoviek, alebo nie.

Úloha

Na vstupe dostanete počet jednotlivých druhov voskoviek a postupnosť zátvoriek. Vašou úlohou je zistiť, či pri danom počte druhov voskoviek mohol na konci dňa, keď všetky deti vrátili svoje voskovky, tento zápis nastať alebo nie.

Formát vstupu

Na prvom riadku vstupu dostanete 4 čísla: \(g\), \(k\), \(s\), \(h\), kde \(g\) je počet guľatých, \(k\) je počet kučeravých, \(s\) je počet špicatých a \(h\) je počet hranatých voskoviek, ktoré majú v škôlke. Platí, že \(0 \leq g,k,s,h \leq 5000\).

Nasleduje \(1\) riadok obsahujúci neprázdnu postupnosť zátvoriek. Dĺžka tejto postupnosti je najviac \(200\,000\).

Formát výstupu

Vypíšte jediný riadok obsahujúci buď reťazec ANO ak je záznam korektný, alebo reťazec NIE ak záznam nie je korektný a teda Marcel musel pri obzeraní Sabinky zmeškať nejaké položenie, zobratie voskovky, alebo nejaké zapísal zle. Nezabudnite na koniec vypísať znak konca riadku.

Príklad

Input:

1 1 1 1
([{<)]}>

Output:

ANO

V škôlke majú z každého druhu voskoviek jeden kus a takýto zápis mohol nastať tak, že zo stola postupne zobrali guľatú, hranatú, kučeravú a špicatú voskovku a následne ich v rovnakom poradí vrátili.

Input:

1 0 0 0
[()]

Output:

NIE

V škôlke majú iba guľatú voskovku a tu hneď na začiatku podľa zápisu niekto zobral hranatú, ktorú ale v škôlke nemajú.

Input:

1 0 0 0
(())

Output:

NIE

V škôlke majú iba jednu guľatú voskovku, ale podľa tohto zápisu sa zo stola najprv zobrali dve guľaté bez toho, aby sa medzi nimi nejaká položila.

Input:

2 0 0 0
(()

Output:

NIE

V škôlke majú dve guľaté voskovky ale v tomto zápise nám chýba položenie jednej voskovky.

Skúsme si najprv povedať, v akých situáciách budeme vedieť zo zápisu zátvoriek povedať, že táto postupnosť nemohla nastať. Sú to tieto situácie:

  • v zápise je, že by sme mali zo stola zobrať nejakú voskovku, ktorá už nie je na stole, alebo ani nikdy na stole nebola

  • v zápise je, že by sme mali vrátiť na stôl nejakú voskovku, ktorú sme si nikdy nezobrali

Ako takéto veci kontrolovať? Jednoducho postupne prechádzame postupnosť zátvoriek a pamätáme si počet voskoviek jednotlivých druhov, ktoré aktuálne sú na stole. Vždy, keď nájdeme nejakú zátvorku, tak si správnym spôsobom zmeníme aktuálny počet voskoviek na stole. Ak sa hocikedy v priebehu stane, že by počet nejakých voskoviek klesol pod \(0\) alebo stúpol nad počet, koľko voskoviek toho druhu máme v škôlke, tak vypíšeme NIE. Netreba zabudnúť skontrolovať, že na konci dňa (na konci vstupu) musia byť na stole všetky voskovky. V prípade ak nie sú, tak tiež vypíšeme NIE. V ostatných prípadoch vypíšeme ANO.

Časová aj pamäťová zložitosť je lineárna, priamo úmerná dĺžke postupnosti zátvoriek.

#include<iostream>

using namespace std;

int main(){
    int max_gulate, max_kucerave, max_spicate, max_hranate;
    int gulate=0, kucerave=0, spicate=0, hranate=0;
    cin>>max_gulate>>max_kucerave>>max_spicate>>max_hranate;
    string vstup;
    getline(cin, vstup); //nacitame znak konca riadku
    getline(cin, vstup);

    for(int i=0;i<vstup.size();i++){
        if(vstup[i]=='(')
            gulate++;
        if(vstup[i]==')')
            gulate--;
        if(vstup[i]=='[')
            hranate++;
        if(vstup[i]==']')
            hranate--;
        if(vstup[i]=='{')
            kucerave++;
        if(vstup[i]=='}')
            kucerave--;
        if(vstup[i]=='<')
            spicate++;
        if(vstup[i]=='>')
            spicate--;

        if(gulate<0 || hranate<0 || kucerave<0 || spicate<0 ||
           gulate>max_gulate || hranate>max_hranate || 
           kucerave>max_kucerave || spicate>max_spicate){
            cout<<"NIE"<<endl;
            return 0;
        }
    }
    
    if(gulate==0&&hranate==0&&kucerave==0&&spicate==0){
        cout<<"ANO"<<endl;
    }else{
        cout<<"NIE"<<endl;
    }
    
    return 0;
}
def spravny(voskovky, k_dispozicii):
    d = {"(":(0,1),"{":(1, 1),"<":(2, 1),"[":(3, 1),")":(0,-1),"}":(1, -1),">":(2, -1),"]":(3, -1)}
    '''
    v d je kluc dany znak voskovky a hodnota je dvojica,
    kde prve cislo je index do pola poctov a 
    druhe cislo je o kolko ho zmenime (plus alebo minus 1)
    '''
    pocty_voskoviek = [0,0,0,0] # kolko voskoviek aktualne mame
    for voskovka in voskovky:
        kde, o_kolko = d[voskovka]
        pocty_voskoviek[kde] += o_kolko
        for i in range(len(pocty_voskoviek)):
            # ak niekedy mame voskoviek menej ako 0 alebo viac ako ich mame k dispozicii
            if pocty_voskoviek[i] < 0 or pocty_voskoviek[i] > k_dispozicii[i]:
                return False

    for i in pocty_voskoviek:
        # ak na konci dna nie su vsetky vratene
        if i != 0:
            return False

    return True

k_dispozicii = list(map(int, input().split()))
voskovky = input()
if spravny(voskovky, k_dispozicii):
    print("ANO")
else:
    print("NIE")

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