Zadanie

Z reaktora sme vybrali trubice s rádioaktívnym odpadom, ktorý potrebujeme ekologicky zlikvidovať. V každej trubici sú zaradom kusy rôznorodých rádioaktívnych látok, pre jednoduchosť ich budeme označovať písmenami az. Ak sa v trubici nachádza za sebou kritické množstvo (dva alebo viac kusov) rovnakej látky, môžeme na tento úsek trubice vystreliť prúd neutrónov a celý tento úsek tým zničiť. Látky v trubici, ktoré boli pred tým na koncoch zničeného úseku budú po tomto vedľa seba.

Ak máme napríklad v trubici látky aabccccbacc môžeme najprv zničiť úsek štyroch látok c a v trubici budú látky aabbacc. Potom môžeme zničiť úsek dvoch látok b, následne troch látok a a napokon zničíme zvyšné látky c.

Týmto postupom by sme zničili celý obsah trubice, avšak ak by sme napríklad najprv zničili úsek látok a, už by sme celý obsah trubice nevedeli zlikvidovať.

Úloha

Máte zadaných niekoľko reťazcov malých písmen anglickej abecedy. Zistite, pre ktoré reťazce dokážeme opakovaným odstraňovaním súvislých úsekov dvoch alebo viacerých rovnakých písmen odstrániť celý reťazec.

Formát vstupu

Na prvom riadku vstupu je prirodzené číslo \(n\) (\(1 \leq n \leq 20\)) udávajúce počet testovacích sád. Nasleduje \(n\) riadkov predstavujúcich jednotlivé testovacie sady, na každom riadku je jeden reťazec písmen az. Dĺžka každého reťazca je aspoň \(1\) a najviac \(200\) znakov.

Presnejšie, v jednotlivých vstupoch (1.in8.in) platí, že dĺžka každého reťazca je zhora obmedzená postupne 5, 10, 20, 40, 80, 160, 200 a 200.

Formát výstupu

Pre každú testovaciu vypíšte jeden riadok obsahujúci slovo ano ak sa dá celý reťazec odstrániť a nie, ak sa nedá.

Príklady

Input:

4
aabccccbacc
bccccbacc
hahaahh
xzzxyzzyzzyx

Output:

ano
nie
nie
ano

Reťazec písmen \(S\) dokážeme celý zmazať práve vtedy, keď platí aspoň jedna z týchto podmienok:

  • \(S\) je prázdny reťazec
  • \(S\) má dĺžku aspoň 2, začína a končí tým istým písmenom, a keď zmažeme všetky výskyty tohto písmena zo začiatku a z konca, dostaneme reťazec, ktorý sa dá zmazať celý. (Čiže napr. “aaaaaUaaa”, kde \(U\) sa dá zmazať, alebo “bbbbbb”).
  • \(S\) sa dá rozseknúť na neprázdne reťazce \(U\) a \(V\), aj \(U\) aj \(V\) sa dajú celé zmazať.
  • \(S\) sa dá rozseknúť na 5 častí \(x,U,x,V,x\), kde \(x\) je ľubovoľné písmeno a \(U\) aj \(V\) sú neprázdne reťazce, ktoré sa dajú celé zmazať.

Dôkaz:

Ľahko overíme, že ak reťazec spĺňa niektorú podmienku, dá za zmazať celý. Stačí nám ukázať, že ak sa reťazec dá zmazať, musí spĺňať aspoň jednu podmienku, čo skúsime ukázať sporom. Majme reťazec, ktorý sa dá zmazať celý ale nespĺňa žiadnu zo štyroch podmienok.

Keď by sme tento reťazec mazali, ako posledné nám musel ostať úsek aspoň dvoch rovnakých písmen, označme si toto písmeno \(x\). Pôvodný reťazec má tvar \(T_0x_1T_1x_2...x_kT_k\), kde \(x_i\) je niekoľko znakov \(x\) a \(T_i\) je reťazec, ktorý sa dá celý zmazať (lebo na konci nám ostali len znaky \(x\).).

Ak \(T_0\) resp. \(T_k\) sú neprázdne, tak daný reťazec sa dá rozseknúť na \(T_0\) a zvyšok, resp. \(T_k\) a zvyšok a teda reťazec spĺňa tretiu podmienku (spor). Ďalej teda predpokladajme, že \(T_0\) aj \(T_k\) sú prázdne.

Ak k je 1, máme reťazec tvaru \(x_1\), ktorý spĺňa druhú podmienku (spor).

Ak k je 2, máme reťazec tvaru \(x_1T_1x_2T_2x_3\). Ak ktorýkoľvek z \(x_1\), \(x_2\), \(x_3\) má aspoň dva znaky, tak reťazec spĺňa tretiu podmienku, inak spĺňa štvrtú (spor).

Ak k je viac ako 2, reťazec spĺňa tretiu podmienku (spor).

\(\square\)

 

Ľahko napíšeme rekurzívnu funkciu, ktorá overí všetky tieto podmienky v čase \(O(n)\), kde \(n\) je dĺžka reťazca, plus čas strávený v rekurzívnych volaniach. Pridáme memoizáciu, aby sme pre každý podúsek vstupného reťazca počítali odpoveď (či sa dá celý zmazať) len raz. Takto dosiahneme časovú zložitosť \(O(n^3)\).

Pamäťová zložitosť je \(O(n^2)\).

Zdrojové kódy budú zverejnené až po 19.8. 23:59:59. Dovtedy sa môžete pokúsiť úlohu naprogramovať sami
(a získať tým nejaké body navyše).

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