Fişierul intrare/ieşire:	c3selector.in, c3selector.out	Sursă	Finala ONIS 2016
Autor	Cosmin-Mihai Tutunaru, Login Iustin Anca	Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	1.25 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

C3selector

Probabil toata lumea a auzit despre pagini web si a vazut tag-uri HTML. La o firma de software din Cluj unde algoritmii intalnesc tehnologia, numita fictiv AlgoTech, una din intrebarile de la interviuri le cere candidatilor sa implementeze un selector de CSS.

O pagina HTML este considerata valida daca respecta urmatoarele conditii:

• are un singur tag parinte; toate celelalte tag-uri sunt copii directi sau indirecti ai tag-ului parinte
• toate tag-urile se deschid cu <tagname> si se inchid cu </tagname>
• un tag poate avea oricati copii, putand avea forma: <x><y><y></y></y><z></z></x>
• un tag poate avea un atribut suplimentar class, avand forma: <tagname class=“classx classy”>
• este posibil ca unele din tag-urile terminale (care nu mai au copii) sa contina un text, putand avea forma: <x><y>text</y><z><y><x>another text</x></y></z></x>
• acelasi tag poate aparea de mai multe ori, posibil cu clase diferite, dar intotdeauna se inchid corect
• o clasa poate aparea de mai multe ori, posibil la tag-uri diferite

Un selector CSS este un pattern folosit pentru a identifica tag-uri intr-un HTML. El poate avea urmatoarele forme:

• div = selecteaza toate tag-urile cu numele div
• div p = selecteaza toate tag-urile p care se afla in interiorul unui tag div
• .intro = selecteaza toate tag-urile care au clasa intro
• .intro.layout = selecteaza toate tag-urile care au atat clasa intro cat si clasa layout ( atentie: este posibil sa apara mai mult de doua clase )
• .layout .header = selecteaza toate tag-urile care au clasa header si se afla in interiorul unui tag care are clasa layout ( atentie: intre cele doua clase exista un spatiu )
• p.big = selecteaza toate tag-urile p care au clasa big
• p .big = selecteaza toate tag-urile cu clasa big care se afla in interiorul unui tag p ( atentie: intre tag si clasa exista un spatiu )

Pe baza formelor mentionate mai sus, un selector CSS poate poate lua toate combinatiile lor, putand avea orice forma. Exemplu: div.a p.q.b i.icon.q.red x y z.x.y.z.a .a.b.c d

Dându-se T teste, fiecare avand o pagina HTML valida si Q selectoare, sa se spuna pentru fiecare selector cate tag-uri distincte poate identifica.

Date de intrare

Fişierul de intrare c3selector.in conţine pe prima linie numărul T, iar pe urmatoarele linii sunt descrise cele T teste. Fiecare test ocupa mai multe linii, in felul urmator:

• O linie avand valoarea Q
• O linie avand un sir de caractere reprezentand un HTML valid
• Q linii avand cate un sir de caractere reprezentant un selector CSS

Date de ieşire

În fişierul de ieşire c3selector.out trebuie sa afisati mai multe linii. Pe fiecare linie se afla un singur numar, reprezentand raspunsul la cate un selector din fisierul de intrare. Raspunsurile trebuie sa apara in ordinea intrebarilor din fisierul de intrare.

Restricţii

• T <= 20
• 1 <= Q <= 1000
• HTML-ul nu poate avea mai mult de 1000 de tag-uri
• Lungimea HTML-ului nu poate avea mai mult de 100.000 de caractere
• Lungimea unui selector CSS nu poate avea mai mult de 1000 de caractere
• Numele unui tag nu poate avea mai mult de 10 de caractere
• Numele unei clase nu poate avea mai mult de 10 de caractere
• HTML-ul poate contine doar: litere mici ale alfabetului englez, <, >, /, =, " sau spatii

Exemplu

Cum se trimit solutii?