시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgXHVjODA0XHVkNjU0XHViYzg4XHVkNjM4XHViOTdjIFx1YzI3ZFx1YWM4YyBcdWM2NzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgXHViYzg4XHVkNjM4XHVhYzAwIDk0MTgzNzI5Nlx1Yzc3OCBcdWIyZjlcdWMyZTBcdWM3NTggXHVjY2I0XHVjMmE0IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgV0hJVEVQQVdOXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM2NzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViYzg4XHVkNjM4XHVhYzAwIDI4NTUzMDRcdWM3NzggXHViMmY5XHVjMmUwXHVjNzU4IFx1YjJmNFx1Yzc4NFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgQlVMTERPR1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNjc4XHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjMjdkXHVhYzhjIFx1YzY3OFx1YzZiMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODAxXHViMmY5XHVkNTVjIFx1YzYwMVx1YzViNCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM5MDRcdWM1ZWNcdWMxMWMgXHVjMjdkXHVhYzhjIFx1YzY3OFx1YzZiOCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHViMmY5XHVjMmUwXHVjNzc0IFx1ZDNjOVx1YzE4Y1x1YzVkMCBcdWM3OTBcdWM4ZmMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YzYwMVx1YzViNCBcdWIyZThcdWM1YjRcdWI0ZTRcdWI5Y2NcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM2MDFcdWM1YjQgXHViMmU4XHVjNWI0XHViODVjIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFlMzBcdWM1YjVcdWQ1NjAgXHViNTRjXHVjNWQwXHViMjk0LCBcdWFjMDEgXHViMmU4XHVjNWI0XHViOTdjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWFmYmMgXHVhYzgzXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzVjOFx1Yzc0NCBcdWI1NGMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjQxOFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgbGV0IGl0IGJlXHViODVjIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM2NzhcdWM2ZTBcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWIyOTQgNTM4MTgyM1x1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgwNFx1ZDY1NFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDBcdWM3OTBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZjlcdWMyZTBcdWM3NzQgXHVjNzkwXHVjOGZjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWM2MDFcdWM1YjQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBuKDEmbGU7biZsZTs1MCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NzQgXHVhY2Y1XHViYzMxIFx1YzVjNlx1Yzc3NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgNTBcdWM3OTBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWNkMWQgXHVkMDZjXHVhZTMwXHViMjk0IDMwMEtCXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVjNjAxXHVjNWI0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggS1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjNjAxXHVjNWI0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O05vIHNvbHV0aW9uLiZxdW90OyBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzMzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaG9uZSBudW1iZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgcHJlc2VudCB3b3JsZCB5b3UgZnJlcXVlbnRseSBtZWV0IGEgbG90IG9mIGNhbGwgbnVtYmVycyBhbmQgdGhleSBhcmUgZ29pbmcgdG8gYmUgbG9uZ2VyIGFuZCBsb25nZXIuIFlvdSBuZWVkIHRvIHJlbWVtYmVyIHN1Y2ggYSBraW5kIG9mIG51bWJlcnMuIE9uZSBtZXRob2QgaG93IHRvIGRvIGl0IGluIGFuIGVhc3kgd2F5IGlzIHRvIGFzc2lnbiBsZXR0ZXJzIHRvIGRpZ2l0cyBhcyBzaG93biBpbiB0aGUgZm9sbG93aW5nIHBpY3R1cmU6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGhvbmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg5cHg7IHdpZHRoOjIzMnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoaXMgd2F5IGV2ZXJ5IHdvcmQgb3IgYSBncm91cCBvZiB3b3JkcyBjYW4gYmUgYXNzaWduZWQgYSB1bmlxdWUgbnVtYmVyLCBzbyB5b3UgY2FuIHJlbWVtYmVyIHdvcmRzIGluc3RlYWQgb2YgY2FsbCBudW1iZXJzLiBJdCBpcyBldmlkZW50IHRoYXQgaXQgaGFzIGl0cyBvd24gY2hhcm0gaWYgaXQgaXMgcG9zc2libGUgdG8gZmluZCBzb21lIHNpbXBsZSByZWxhdGlvbnNoaXAgYmV0d2VlbiB0aGUgd29yZCBhbmQgdGhlIHBlcnNvbiBpdHNlbGYuIFNvIHlvdSBjYW4gbGVhcm4gdGhhdCB0aGUgY2FsbCBudW1iZXIgOTQxODM3Mjk2IG9mIGEgY2hlc3MgcGxheWluZyBmcmllbmQgb2YgeW91cnMgY2FuIGJlIHJlYWQgYXMgV0hJVEVQQVdOLCBhbmQgdGhlIGNhbGwgbnVtYmVyIDI4NTUzMDQgb2YgeW91ciBmYXZvdXJpdGUgdGVhY2hlciBpcyByZWFkIEJVTExET0cuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIHRoZSBzaG9ydGVzdCBzZXF1ZW5jZSBvZiB3b3JkcyAoaS5lLiBvbmUgaGF2aW5nIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBudW1iZXIgb2Ygd29yZHMpIHdoaWNoIGNvcnJlc3BvbmRzIHRvIGEgZ2l2ZW4gbnVtYmVyIGFuZCBhIGdpdmVuIGxpc3Qgb2Ygd29yZHMuIFRoZSBjb3JyZXNwb25kZW5jZSBpcyBkZXNjcmliZWQgYnkgdGhlIHBpY3R1cmUgYWJvdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBmaWxlIFBIT05FLklOIGNvbnRhaW5zIHRoZSBjYWxsIG51bWJlciwgdGhlIHRyYW5zY3JpcHRpb24gb2Ygd2hpY2ggeW91IGhhdmUgdG8gZmluZC4gVGhlIG51bWJlciBjb25zaXN0cyBvZiBhdCBtb3N0IDEwMCBkaWdpdHMuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgdG90YWwgbnVtYmVyIG9mIHRoZSB3b3JkcyBpbiB0aGUgZGljdGlvbmFyeSAobWF4aW11bSBpcyA1MDAwMCkuIEVhY2ggb2YgdGhlIHJlbWFpbmluZyBsaW5lcyBjb250YWlucyBvbmUgd29yZCwgd2hpY2ggY29uc2lzdHMgb2YgbWF4aW1hbGx5IDUwIHNtYWxsIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIFRoZSB0b3RhbCBzaXplIG9mIHRoZSBpbnB1dCBmaWxlIGRvZXNuJiMzOTt0IGV4Y2VlZCAzMDBLQi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBmaWxlIFBIT05FLk9VVCBjb250YWlucyB0aGUgc2hvcnRlc3Qgc2VxdWVuY2Ugb2Ygd29yZHMgd2hpY2ggaGFzIGJlZW4gZm91bmQgYnkgeW91ciBwcm9ncmFtLiBUaGUgd29yZHMgYXJlIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBJZiB0aGVyZSBpcyBubyBzb2x1dGlvbiB0byB0aGUgaW5wdXQgZGF0YSwgdGhlIGxpbmUgY29udGFpbnMgdGV4dCBgTm8gc29sdXRpb24uJiMzOTsuIElmIHRoZXJlIGFyZSBtb3JlIHNvbHV0aW9ucyBoYXZpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHdvcmRzLCB5b3UgY2FuIGNob29zZSBhbnkgc2luZ2xlIG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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