Problem B. Magicka

概要

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

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

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

問題

あなたはウィザードとして 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 は相反する元素であると仮定する。

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

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

入力

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 の左から順にすべての元素を呼び出さなくてはいけない。

出力

Case #x: y
...

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

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

制限

1 ≦ T ≦ 100

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

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

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

データセット(小)

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

データセット(大)

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

サンプル入出力

入力

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: []

ヒント

提出・原文

http://code.google.com/codejam/contest/dashboard?c=975485#s=p1

回答例

作成者	ソースコード
pine[e]	GCJ_2011QRB_Magicka.cpp

[入力欄を追加]