TITLE: Problem B. Magicka

#contents

#br

* 概要 [#f171457c]

Magicka™ は「アローヘッドゲームスタジオ」によって開発されたアクション・アドベンチャーゲームだ。

Magicka ではあなたはウィザードである。あなたは、元素を呼び出し、それを組み合わせることで、Magicka を生み出すことができる。

Magika を生み出すには、他の方法があるかも知れないが、今回はそれはできないと仮定してよい。

* 問題 [#ye451a95]

あなたはウィザードとして 8 つの基本元素を呼び出すことができる。
それらの元素は 「Q, W, E, R, A, S, D, F」という一文字のアルファベットで表す。

あなたが元素を呼び出す時、それがあなたの元素リストに加えられる。

たとえば、あなたが W を呼び出し、その後 A を呼び出した場合 (以降「WA を呼び出す」と略記する)、要素リストは [W, A] のようになる。

私たちは、基本元素を組み合わせで、残る 18 文字の特別な非基本元素を作ろうと思う。

たとえば、Q と F 組み合わせると T になるとする。その2つが元素リストに加えられた場合 、その2つの元素は元素リストから削除され、T によって置き換えられる。

元素リストが、[A, Q, F] もしくは [A, F, Q] の場合も、上の例と同じように Q と F が T に置き換えられ、要素リストは [A, T] となる。

私たちは、相反する基本元素の組み合わせを指定する。

あなたが元素を呼び出したあと、元素リストの末尾が組み合わせ通りになっていれば、その元素の組み合わせが呼び出されるのは既に説明した。

そしてその後、相反する元素が元素リストに存在した場合、元素リストがクリアされる。

たとえば、Q と F 組み合わせると T になるとする。
そして、R と F は相反する元素であると仮定する。

その際に、以下の元素を呼び出した場合、結果は次のようになる。

|呼び出した元素|呼び出した後の元素リスト|補足|h
|~QF|[T]|Q と F が組み合わされて T になった|
|~QEF|[Q, E, F]|Q と F が元素リストの末尾に連続していなかったので、組み合わせられない|
|~RFE|[E]|F と R は相反する元素であるため、途中で元素リストがクリアされた|
|~REF|[]|F と R は相反する元素であるため、途中で元素リストがクリアされた|
|~RQF|[R, T]|QF の組み合わせにより T つくられ、リストがクリアされた|
|~RFQ|[Q]|F と R は相反する元素であるため、途中で元素リストがクリアされた|

あなたには、呼び出す元素の一覧が与えられた時、それを実際に呼び出したあとに、元素リストがどうなっているかを求めて欲しい。

* 入力 [#a60d86ca]

#pre{{
T
C s D t N u
...
}}

1行目にはデータセットの個数 T が与えられる。
2行目から (T+1) 行目に、データセットが改行区切りで T 個与えられる。

一つのデータセットは、複数の値をスペースで区切りったものである。

初めの整数 C は元素の組み合わせの個数である。
次は C 個の文字列 s である。
s は3文字の文字列であり、たとえば「QFT」という文字列だった場合、Q と F を組み合わせると T になることを表している。

次の整数 D は相反する元素をの組み合わせの個数を表す。
次は D 個の文字列 t である。
t は2文字の文字列であり、たとえば「RF」という文字列だった場合、R と F を同時に呼び出してはいけないことを表す。

次の整数 N はあなたが呼び出す元素の個数である。
最後は、あなたが呼び出す元素を表す N 文字の文字列 u である。
あなたは、文字列 u の左から順にすべての元素を呼び出さなくてはいけない。

* 出力 [#n543917e]

#pre{{
Case #x: y
...
}}

データセットごとに、データセットの番号 x (1 からはじまる) と、元素リスト y を出力せよ。

元素リスト y は、[A, B, C] のような形式で出力しなければいけない。
前後を括弧で囲み、値の区切りにはコンマを用いる。


* 制限 [#a9204de2]

1 ≦ T ≦ 100

あなたが呼び出す元素 u は、非基本元素をつくる組み合わせのみで構成されるかもしれないし、相反する元素のみで構成されるかもしれない。

同じ元素同士が相反することはできない。

ゲーム版の Magickaの とは異なり、元素リストの長さに制限はない。

** データセット(小) [#qa0bf9b9]

0 ≦ C ≦ 1
0 ≦ D ≦ 1
1 ≦ N ≦ 10

** データセット(大) [#jcf33008]

0 ≦ C ≦ 36
0 ≦ D ≦ 28
1 ≦ N ≦ 100

* サンプル入出力 [#w009d9fb]

** 入力 [#maccb721]

#pre{{
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
}}

** 出力 [#e1d56122]

#pre{{
Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []
}}

* ヒント [#ta8323a0]

#region
深く考えずに、問題のまま実装すればいいです。
相反の判定が、組み合わせの判定の後であることに注意。
#endregion

* 提出・原文 [#y62db8a6]
http://code.google.com/codejam/contest/dashboard?c=975485#s=p1
* 回答例 [#ude52e49]
|作成者|ソースコード|
|&areaedit(){pine};|&attachref(./GCJ_2011QRB_Magicka.cpp);|
[&addline(file,above){入力欄を追加};]

#br

-----

#pcomment