시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 2 2 66.667%

문제

핸드폰의 문자메시지 기능 외에도, 일반 전화기의 각 숫자에 영어 알파벳이 할당되어 있는 경우가 종종 있다. 예를 들어 아래와 같이 각 숫자에 문자가 할당된 경우를 보자.

	1 ij	2 abc	3 def
	4 gh	5 kl	6 mn
	7 prs	8 tuv	9 wxy
		0 oqz

이와 같은 알파벳을 이용하면 전화번호를 쉽게 외울 수 있다. 예를 들면, 번호가 941837296인 당신의 체스 친구의 번호를 WHITEPAWN과 같이 외울 수 있고, 번호가 2855304인 당신의 담임선생님의 번호를 BULLDOG과 같이 외울 수 있다.

어떤 번호가 주어졌을 때, 당신은 그 번호를 쉽게 외우기 위해 적당한 영어 단어들을 찾으려고 한다. 이때 가능하면 단어의 개수를 줄여서 쉽게 외울 수 있도록 하려 한다. 또한, 당신이 평소에 자주 사용하는 영어 단어들만을 사용하려고 한다.

여러 개의 영어 단어로 번호를 기억할 때에는, 각 단어를 숫자로 바꾼 것이 연결되었을 때 번호가 되면 된다. 예를 들어 let it be로 번호를 외웠을 때, 이는 5381823가 된다.

입력

첫째 줄에 전화번호가 공백 없이 주어진다. 이 길이는 100자를 넘지 않는다. 다음 줄에는 당신이 자주 사용하는 영어 단어의 개수 n(1≤n≤50,000)이 주어진다. 다음 n개의 줄에는 각 단어들이 공백 없이 알파벳 소문자로 주어진다. 각 단어의 길이는 50자를 넘지 않는다. 입력 파일의 총 크기는 300KB를 넘지 않는다.

출력

첫째 줄에 사용한 영어 단어의 개수 K를 출력한다. 다음 K개의 줄에는 차례로 영어 단어를 출력한다. 정답이 없는 경우에는 "No solution." 을 출력한다.

예제 입력 1

7325189087
5
it
your
reality
real
our

예제 출력 1

2
reality
our

예제 입력 2

2285064252258219
5
long
false
cat
tail
black

예제 출력 2

0
No solution.
W3sicHJvYmxlbV9pZCI6IjIzMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWQ2NTRcdWJjODhcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU3OFx1YjRkY1x1ZDNmMFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWJhNTRcdWMyZGNcdWM5YzAgXHVhZTMwXHViMmE1IFx1YzY3OFx1YzVkMFx1YjNjNCwgXHVjNzdjXHViYzE4IFx1YzgwNFx1ZDY1NFx1YWUzMFx1Yzc1OCBcdWFjMDEgXHVjMjJiXHVjNzkwXHVjNWQwIFx1YzYwMVx1YzViNCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzQgXHVkNTYwXHViMmY5XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjODg1XHVjODg1IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWMwMSBcdWMyMmJcdWM3OTBcdWM1ZDAgXHViYjM4XHVjNzkwXHVhYzAwIFx1ZDU2MFx1YjJmOVx1YjQxYyBcdWFjYmRcdWM2YjBcdWI5N2MgXHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cHJlPlxyXG5cdDEgaWpcdDIgYWJjXHQzIGRlZlxyXG5cdDQgZ2hcdDUga2xcdDYgbW5cclxuXHQ3IHByc1x0OCB0dXZcdDkgd3h5XHJcblx0XHQwIG9xelxyXG48XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgXHVjODA0XHVkNjU0XHViYzg4XHVkNjM4XHViOTdjIFx1YzI3ZFx1YWM4YyBcdWM2NzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgXHViYzg4XHVkNjM4XHVhYzAwIDk0MTgzNzI5Nlx1Yzc3OCBcdWIyZjlcdWMyZTBcdWM3NTggXHVjY2I0XHVjMmE0IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgV0hJVEVQQVdOXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM2NzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViYzg4XHVkNjM4XHVhYzAwIDI4NTUzMDRcdWM3NzggXHViMmY5XHVjMmUwXHVjNzU4IFx1YjJmNFx1Yzc4NFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgQlVMTERPR1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNjc4XHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjMjdkXHVhYzhjIFx1YzY3OFx1YzZiMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODAxXHViMmY5XHVkNTVjIFx1YzYwMVx1YzViNCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzkwNFx1YzVlY1x1YzExYyBcdWMyN2RcdWFjOGMgXHVjNjc4XHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWIyZjlcdWMyZTBcdWM3NzQgXHVkM2M5XHVjMThjXHVjNWQwIFx1Yzc5MFx1YzhmYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjNjAxXHVjNWI0IFx1YjJlOFx1YzViNFx1YjRlNFx1YjljY1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YzYwMVx1YzViNCBcdWIyZThcdWM1YjRcdWI4NWMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWUzMFx1YzViNVx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQsIFx1YWMwMSBcdWIyZThcdWM1YjRcdWI5N2MgXHVjMjJiXHVjNzkwXHViODVjIFx1YmMxNFx1YWZiYyBcdWFjODNcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViNDE4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBsZXQgaXQgYmVcdWI4NWMgXHViYzg4XHVkNjM4XHViOTdjIFx1YzY3OFx1YzZlMFx1Yzc0NCBcdWI1NGMsIFx1Yzc3NFx1YjI5NCA1MzgxODIzXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODA0XHVkNjU0XHViYzg4XHVkNjM4XHVhYzAwIFx1YWNmNVx1YmMzMSBcdWM1YzZcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhZTM4XHVjNzc0XHViMjk0IDEwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWM3OTBcdWM4ZmMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YzYwMVx1YzViNCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4IG4oMSZsZTtuJmxlOzUwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc3NCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCA1MFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjXHVjNzU4IFx1Y2QxZCBcdWQwNmNcdWFlMzBcdWIyOTQgMzAwS0JcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWM2MDFcdWM1YjQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBLXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM2MDFcdWM1YjQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7Tm8gc29sdXRpb24uJnF1b3Q7IFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjMzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBob25lIG51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBwcmVzZW50IHdvcmxkIHlvdSBmcmVxdWVudGx5IG1lZXQgYSBsb3Qgb2YgY2FsbCBudW1iZXJzIGFuZCB0aGV5IGFyZSBnb2luZyB0byBiZSBsb25nZXIgYW5kIGxvbmdlci4gWW91IG5lZWQgdG8gcmVtZW1iZXIgc3VjaCBhIGtpbmQgb2YgbnVtYmVycy4gT25lIG1ldGhvZCBob3cgdG8gZG8gaXQgaW4gYW4gZWFzeSB3YXkgaXMgdG8gYXNzaWduIGxldHRlcnMgdG8gZGlnaXRzIGFzIHNob3duIGluIHRoZSBmb2xsb3dpbmcgcGljdHVyZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waG9uZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODlweDsgd2lkdGg6MjMycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhpcyB3YXkgZXZlcnkgd29yZCBvciBhIGdyb3VwIG9mIHdvcmRzIGNhbiBiZSBhc3NpZ25lZCBhIHVuaXF1ZSBudW1iZXIsIHNvIHlvdSBjYW4gcmVtZW1iZXIgd29yZHMgaW5zdGVhZCBvZiBjYWxsIG51bWJlcnMuIEl0IGlzIGV2aWRlbnQgdGhhdCBpdCBoYXMgaXRzIG93biBjaGFybSBpZiBpdCBpcyBwb3NzaWJsZSB0byBmaW5kIHNvbWUgc2ltcGxlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIHRoZSB3b3JkIGFuZCB0aGUgcGVyc29uIGl0c2VsZi4gU28geW91IGNhbiBsZWFybiB0aGF0IHRoZSBjYWxsIG51bWJlciA5NDE4MzcyOTYgb2YgYSBjaGVzcyBwbGF5aW5nIGZyaWVuZCBvZiB5b3VycyBjYW4gYmUgcmVhZCBhcyBXSElURVBBV04sIGFuZCB0aGUgY2FsbCBudW1iZXIgMjg1NTMwNCBvZiB5b3VyIGZhdm91cml0ZSB0ZWFjaGVyIGlzIHJlYWQgQlVMTERPRy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIHNob3J0ZXN0IHNlcXVlbmNlIG9mIHdvcmRzIChpLmUuIG9uZSBoYXZpbmcgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG51bWJlciBvZiB3b3Jkcykgd2hpY2ggY29ycmVzcG9uZHMgdG8gYSBnaXZlbiBudW1iZXIgYW5kIGEgZ2l2ZW4gbGlzdCBvZiB3b3Jkcy4gVGhlIGNvcnJlc3BvbmRlbmNlIGlzIGRlc2NyaWJlZCBieSB0aGUgcGljdHVyZSBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZpbGUgUEhPTkUuSU4gY29udGFpbnMgdGhlIGNhbGwgbnVtYmVyLCB0aGUgdHJhbnNjcmlwdGlvbiBvZiB3aGljaCB5b3UgaGF2ZSB0byBmaW5kLiBUaGUgbnVtYmVyIGNvbnNpc3RzIG9mIGF0IG1vc3QgMTAwIGRpZ2l0cy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRoZSB0b3RhbCBudW1iZXIgb2YgdGhlIHdvcmRzIGluIHRoZSBkaWN0aW9uYXJ5IChtYXhpbXVtIGlzIDUwMDAwKS4gRWFjaCBvZiB0aGUgcmVtYWluaW5nIGxpbmVzIGNvbnRhaW5zIG9uZSB3b3JkLCB3aGljaCBjb25zaXN0cyBvZiBtYXhpbWFsbHkgNTAgc21hbGwgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gVGhlIHRvdGFsIHNpemUgb2YgdGhlIGlucHV0IGZpbGUgZG9lc24mIzM5O3QgZXhjZWVkIDMwMEtCLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IGZpbGUgUEhPTkUuT1VUIGNvbnRhaW5zIHRoZSBzaG9ydGVzdCBzZXF1ZW5jZSBvZiB3b3JkcyB3aGljaCBoYXMgYmVlbiBmb3VuZCBieSB5b3VyIHByb2dyYW0uIFRoZSB3b3JkcyBhcmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIElmIHRoZXJlIGlzIG5vIHNvbHV0aW9uIHRvIHRoZSBpbnB1dCBkYXRhLCB0aGUgbGluZSBjb250YWlucyB0ZXh0IGBObyBzb2x1dGlvbi4mIzM5Oy4gSWYgdGhlcmUgYXJlIG1vcmUgc29sdXRpb25zIGhhdmluZyB0aGUgbWluaW11bSBudW1iZXIgb2Ygd29yZHMsIHlvdSBjYW4gY2hvb3NlIGFueSBzaW5nbGUgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Central European Olympiad in Informatics > CEOI 1999 2번

  • 빠진 조건을 찾은 사람: kcm1700