YUHA presents C88 謎解き×競技プログラミング 『ある勇者の物語』

C - 酒場の冒険者たち


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

実装難易度★★★☆☆
謎解き難易度★☆☆☆☆

問題文

あなたは生まれ育った村を旅立ち、冒険者が集う街へとやってきた。
酒場で仲間になってくれそうな冒険者を探したところ、
複数の冒険者が名乗りを上げてくれた。
ところが、あなたは直感的に冒険者達の中に良い冒険者と悪い冒険者がいるのを感じた。
あなたはは良い冒険者は必ず本当のことを言い、
悪い冒険者は必ず嘘をつくということを知っている。
それぞれの冒険者が「****は良い/悪い冒険者だ」と言うので、
良い冒険者の名前を挙げよ。

入力

入力は以下の形式で標準入力から与えられる。
N
S_1
S_2
...
S_N
U_1 is a V_1 venturer.
U_2 is a V_2 venturer.
...
U_N is a V_N venturer.
  • 1 行目には酒場にいる冒険者の人数 N (1 ≦ N ≦ 20) が与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目の冒険者の名前 S_i が与えられる。
    • S_i は大文字英アルファベットからなる。
    • S_i の長さ |S_i|1 ≦ |S_i| ≦ 20 を満たす。
    • i ≠ j のとき S_i ≠ S_j が保証される。
  • N + 2 行目からの N 行のうち i 行目には i 番目の冒険者の発言が与えられる。各冒険者の発言中の各変数は以下の制約を満たす。
    • U_i は冒険者の名前のうちのいずれかである。
    • V_igood または bad のいずれかである。

出力

良い冒険者の名前を 1 行にひとつずつ、辞書順でソートして出力せよ。
複数の解が考えられる場合は、良い冒険者の人数が最も多い解を出力せよ。
良い冒険者の人数が最も多い解が複数存在する場合は、
それらの解の中で辞書順で最も若い解を出力せよ。
解が存在しない場合は No answers と出力せよ。
出力の末尾に改行を入れること。
解が存在する場合、入力で与えられる冒険者の中に 1 人以上良い冒険者が含まれることが保証されている。

入力例 1

1
ARTHUR
ARTHUR is a good venturer.

出力例 1

ARTHUR

入力例 2

2
CAIN
COOKIE
COOKIE is a good venturer.
CAIN is a good venturer.

出力例 2

CAIN
COOKIE

入力例 3

2
KONAN
TONNELAT
TONNELAT is a bad venturer.
KONAN is a bad venturer.

出力例 3

KONAN

入力例 4

2
PAOLO
LAND
LAND is a good venturer.
PAOLO is a bad venturer.

出力例 4

No answers

Submit提出する