D - 語呂合わせ
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
日本には数字と短い文字列を対応させる語呂合わせの文化がある。
このことに興味を持った高橋君は、1 以上 K 以下の数字のみからなる正整数 v_1, v_2, ... , v_N とそれぞれの正整数に対応する文字列 w_1, w_2, ... , w_N の組 (v_1, w_1), (v_2, w_2), ... , (v_N, w_N) から、どの数字がどの文字列に対応しているかを推論することにした。
すなわち、以下の条件を満たす K 個の文字列 s_1, s_2, ... , s_K を求めたい。
- 1≦i≦K を満たす任意の整数 i に対して、1≦|s_i|≦3 を満たす。
- 1≦i≦N を満たす任意の整数 i に対して、整数 v_i を桁ごとに分解した際に得られる数字が上から順に d_1, d_2, ... , d_l としたとき、文字列 s_{d_1}, s_{d_2}, ... , s_{d_l} をこの順に連結した文字列が w_i に等しい。
K 個の文字列 s_1, s_2, ... , s_K を出力するプログラムを作成せよ。
入力
入力は以下の形式で標準入力から与えられる。
K N v_1 w_1 v_2 w_2 : v_N w_N
- 1 行目には、整数 K (1≦K≦9) と N (1≦N≦50) が空白区切りで与えられる。
- 2 行目から N 行には、数字と文字列の組に関する情報が与えられる。N 行のうち i (1≦i≦N) 行目には 1 以上 K 以下の数字のみからなる整数 v_i (1≦v_i≦10^9) と半角小文字英字のみからなる文字列 w_i (1≦|w_i|≦27) が空白区切りで与えられる。
- 1 以上 K 以下のどの数字も v_1, v_2, ... , v_N のうち 1 つ以上に登場する。
- 与えられる入力では、条件を満たす K 個の文字列 s_1, s_2, ... , s_K は必ず存在する。
部分点
この問題には部分点が設定されている。
- K ≦ 3 かつ w_1 から w_N までのどの文字列も
a
,b
,c
のいずれかのみで構成されているデータセット 1 に正解した場合は、40 点が与えられる。 - 追加制約のないデータセット 2 に正解した場合は、上記とは別に 60 点が与えられる。
出力
出力は K 行からなる。K 行のうち i (1≦i≦K) 行目には文字列 s_i を出力せよ。
条件を満たす K 個の文字列の組み合わせが複数存在する場合は、それらの組み合わせのうちどの 1 つを出力してもよい。
出力の末尾にも改行を入れること。
入力例1
6 4 356 migoro 461 yoroi 2 ni 12 ini
出力例1
i ni mi yo go ro
この入力例では、s_1 = i
, s_2 = ni
, s_3 = mi
, s_4 = yo
, s_5 = go
, s_6 = ro
と置くことによって題意を満たす K 個の文字列とすることができる。実際に、
- v_1 = 356 を桁ごとに分解した場合に 3, 5, 6 が得られ、s_3 =
mi
, s_5 =go
, s_6 =ro
をこの順に連結した文字列migoro
は w_1 に等しい。 - v_2 = 461 を桁ごとに分解した場合に 4, 6, 1 が得られ、s_4 =
yo
, s_6 =ro
, s_1 =i
をこの順に連結した文字列yoroi
は w_2 に等しい。 - v_3 = 2 を桁ごとに分解した場合に 2 が得られ、s_2 =
ni
は w_3 に等しい。 - v_4 = 12 を桁ごとに分解した場合に 1, 2 が得られ、s_1 =
i
, s_2 =ni
をこの順に連結した文字列ini
は w_4 に等しい。
なお、この入力例はデータセット 1 の条件を満たさないことに注意せよ。
入力例2
3 4 21 aaa 12 aaa 123 aaaaaa 13 aaaa
出力例2
a aa aaa
入力例3
2 3 12211 abcaaaaabcabc 2121 aaabcaaabc 222221 aaaaaaaaaaabc
出力例3
abc aa
入力例4
2 1 12 abcab
出力例4
ab cab