S - Schizobrazec

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Poznáte ten pocit, kedy ani neviete, či vám je smutno alebo veselo? Nie? Dobre vám tak!
Predstavte si ale obraz, ktorý ani nevie, akej je farby! Nie je to tak jednoduché ako spočítať pixely elementárnych farieb a zistiť, ktoých je viac. Tento obraz ich totiž nemá, je kvadrantový.
Aby toho nebolo málo, ten istý obraz môže byť zároveň 3-modrý aj 2-červený a tak jeho predstava o vlastnej farbe sa líši podľa toho, ako sa ktorý deň zobudí.

Dnes sa cítim na úroveň 16

Kvadrantovým obrazom rozumieme taký, ktorý, ak to potrebuje, je rozdelený na kvadranty(rovnako veľké štvrtiny : ľavá horná, pravá horná, ľavá dolná, pravá dolná, v tomto poradí)
S rastúcim počtom farieb a kombinácií rastie aj náročnosť na popísanie kvadrantového obrazu, tak sa obmedzíme len na dve farby (označme ich 1 a 2) a výskyt oboch bude daný samostaným jednofarebným obrazom, ktorý budeme nazývať kvadrantovou farebnou maskou.

Kvadranotvá maska je daná formou textového reťazca R s odvodením:

R -> Q
Q -> (QQQQ) | F | V

Maska je buď plne zafarbená - "F", prázdna - "V" alebo čiastočne zafarbená.
V tom prípade sa rozdelí na 4 kvadranty (ozátvorkované, aby bolo jasné, že patria spolu) (v poradí ľavý horný, pravý horný, ľavý dolný, pravý dolný) a pre každý kvadrant sa potom aplikujú tie isté pravidlá.

Nástroj na pohranie sa s takouto reprezentáciou je tu

Platnými reťazcami sú napríklad:

F
V
(FFFF) ( ekvivalentné s F )
(F(FVFF)(FFVF)F)

Neplatnými reťazcami sú napríklad:

FF - na nultej úrovni je dovolený len jeden prvok alebo zátvorky
(FFF) , ((FFVF)) - málo kvadrantov v zátvorke
(FFFFF) - veľa kvadrantov v zátvorke
(FF)FVVF(F), (FFVF)) - zle ozátvorkovaný výraz
(FQVF) neplatný znak, povolené sú len F,V,( a ) (ani medzera)

Hovoríme, že obraz je na úrovni U farby F, ak vo väčšine dielikov úrovne U prevláda farba F:

Pre každý dielik úrovne U zistíme, ktorá farba v ňom prevláda
1. Farba 1
2. Farba 2
3. Ani jedna, sú zastúpené rovnako
Zistíme počet dielikov, kde prevláda farba 1 a kde farba 2
Odpoveďou bude:
- 1, ak vo väčšine dielikov prevláda farba 1
- 2, ak vo väčšine dielikov prevláda farba 2
- 0, inak

Úroveň dielika je v konečnom dôsledku počet zátvoriek, v ktorých sa nachádza. Keby bol obraz úplne rozdelený, na x-tej úrovni by bolo 4^x rovnako veľkých dielikov.

Úloha

Pre danú úroveň a kvadrantové farebné masky obrazu zistite, ako sa dnes obraz cíti.

Vstup

V prvom riadku vstupu sa nachádza počet testovacích sád S

Každá sada začína riadkom s celým číslom U

Nasledujúce dva riadky obsahujú textové reťazce R1 a R2 popisujúce kvadrantové masky pre farbu 1 a farbu 2

1 ≤ S ≤ 50
0 ≤ U ≤ 20
1 ≤ |R1|,|R2| ≤ 10 000

Výstup

Výstupom programu je pre každú sadu číslo prevládajúcej farby na úrovni U.
Ak žiadna neprevláda, vypíšte 0.

Príklad

Vstup:

4
2
F
((((FVFV)VFV)FVF)VFV)
3
(FVVF)
(V(FVVV)(VVFV)(FFFV))
1
((FFFV)VFV)
((VVVF)FVF)
2
((FFFV)VFV)
((VVVF)FVF)

Výstup:

12 Finále 2