新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
偽の硬貨
問題 
サリー・ジョンズは1ダースのヴォヤジャー銀貨を持っている。しかし、そのうち11個のみが本物の銀貨であり、残りの1つは色と大きさが本物の銀貨に似せてある偽物である。偽のコインは他のコインと重さが違うが、サリーは偽物が本物より重いのか軽いのかは知らない。
幸運なことに、サリーにとても正確な上皿天秤を貸してくれる友達がいる。その友達はサリーに、偽物のコインを見つけるために3回はかることを許している。例えば、2つのコインが上皿天秤で釣りあったとき、彼女はその2つのコインは本物であるとわかる。今度は、本物だとわかっているコインと3つ目のコインを比較して釣りあわなかったら、サリーは3つめのコインが偽物であることがわかり、それが軽いか重いかも天秤が傾いた方向によって決定できる。
彼女がはかりの方法を慎重に選べば、サリーは必ず偽物のコインをちょうど3回のはかりで決定することができる。
入力
入力の最初の行にはテストケースの数をあらわす整数n(n>0)が書かれている。各テストケースは3行の入力からなり、それぞれがはかりの操作に対応する。サリーは各々のコインをAからLまでのアルファベットで識別している。はかりの情報は2つのアルファベットの列と「up」「down」「even」のうちどれか1つが空白を区切りとして書かれている。最初のアルファベットの列は天秤の左側の皿に乗せたコインをあらわす。次のアルファベットの列は天秤の右側の皿に乗せたコインをあらわす。(サリーは常に左右の皿に同じ数のコインを乗せる。)3つめにある文字列は天秤の右側の皿が上がったか下がったか、釣りあったかをあらわす。
出力
各ケースについて、どのコインが重い(heavy)または軽い(light)かを、そのコインを識別するアルファベットとともに出力せよ。解は必ず定まるとしてよい。
入力例
1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even
出力例
K is the counterfeit coin and it is light.
出典
East Central North America 1998
