Programozás‎ > ‎Feladatok‎ > ‎

Varázslat

Egy játékban varázslók lehetünk és elemeket idézhetünk meg. Nyolc alapvető elem létezik, ezeket a következő karakterek jelölik:
{Q,W,E,R,A,S,D,F}. Amikor megidézünk egy elemet, az felkerül az elemeinket tartalmazó lista végére. Például ha először az A, majd utána a W elemet idézzük meg, akkor listánk így néz ki: [A,W].

Bizonyos alapvető elemek össze tudnak kombinálódni, és így új elemek keletkezhetnek. Ezek az új elemek különböznek az alapvető elemektől, és az angol ábécé további 18 betűjével jelöljük őket. Például egy Q és egy F összekombinálódhat és így létrejöhet például egy T. Ez csak akkor következik be, ha a két kombinálódásra képes elem a lista végén, egymás mellett jelent meg. Ilyenkor rögtön törlődnek a listáról, és az általuk létrehozott új elem kerül a helyükre, a lista végén. Az előző példát folytatva, ha az elemek listája [A,Q,F] vagy [A,F,Q], akkor rögtön átalakul, és [A,T] lesz belőle.

Vannak olyan alapvető elemek is, amelyek ellentétesek. Ha egy elemet megidéztünk, és nem kombinálódott össze új elemmé, de a lista valamelyik korábbi elemével ellentétes, akkor a teljes lista törlődik. Például ha Q és F T-vé kombinálódik, továbbá R és F ellentétes, akkor a következők történhetnek:
  • QF → [T] (Q és F összekombinálódik T-vé)
  • QEF → [Q, E, F] (Q és F nem szomszédos, nem kombinálódnak)
  • RFE → [E] (F és R ellentétes, a lista törlődik, majd E-t idéztük meg)
  • REF → [] (F és  R ellentétes, a lista törlődik)
  • RQF → [R, T] (QF átalakul T-vé, ezért a lista nem törlődik)
  • RFQ → [Q] (F és  R ellentétes, a lista törlődik, ...)

Feladat

Írjunk programot, ami a megidézett elemek ismeretében megadja, hogy végül mi maradt az elem-listában!

Bemenet

A bemenet első sora a tesztesetek T számát adja meg (1 ≤ T ≤ 100), ezután T sorban egy-egy teszteset következik. Minden teszteset egyetlen, szóközökkel tagolt sor, ami a következő módon épül fel:
  • Először egy C egész áll (0 ≤ C ≤ 36), majd C karakterlánc, mindegyik 3 betűt tartalmaz, a két alapvető elem, és a belőlük kombinálódó harmadik elem betűjelét.
  • Ezután egy D egész jön (0 ≤ D ≤ 28), majd D darab kétbetűs karakterlánc, az ellentétes elemek párjai.
  • Végül egy N egész következik (1 ≤ N ≤ 100), és utána egy N karakter hosszú karakterlánc, a megidézett elemek sorozata.

Kimenet

Minden tesztesethez írjuk ki a végül megmaradó elem-listát, a példának megfelelő formátumban.

Példa

Bemenet  Kimenet
5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW
Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []


Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2011 Qualification Round (link)
Algoritmusok: listakezelés, karakterláncok lexikális elemzése