Koniec kola: 1. november 2021 23:59
5 dní
Počet bodov:
Popis:  12b
Program:  8b

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.

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.