奧賽天地電話號碼
在現在社會,你會經常面對許多電話號碼,而且它們變得超越來越長,但你要記住一些號碼。一種比較簡單的辦法是將數字與它上面的字母關聯起來(如下圖所示)
這樣每個詞或一組單詞就指定到一個唯一的數。于是你只要記住這些單詞,而不是去這些數碼。如何能找到與某人自身有一定聯系的單詞,則它對應的電話號碼無疑是非常吸引人的。例如,你就可以將一個電話號碼為941837296的棋友記為whitepawn(白卒), 你喜愛的老師的號碼2855304可記為bulldog。
你的任務是寫一個程序,找出最少的單詞序列,使得它符合給定的電話號碼與一些單詞列表。數字與字母的對應關系如上圖如示。
輸入
輸入文件 phone.in 的第一行包含一個電話號碼(最多100個數字)。第二行包含一個整數,表示給定字典的單詞數(最大不超過50000)。接下來的行每行包含一個單詞(最多50個小寫字母),整個輸入文件不超過300kb。
輸出
輸出文件 phone.out 僅有一行 ,包含所求的最少的單詞序列,單詞之間用一個空格分開。如果無解,則輸出`no solution',如果有多種解,則你可輸出任意一個。
樣例
phone.in
7325189087
5
it
your
reality
real
our
phone.out
reality our
( 符號電話號碼的另一解答為`real it your',它包含三個單詞).
phone.in
4294967296
5
it
your
reality
real
our
phone.out
no solution.
<