시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 3 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." 을 출력한다.

예제 입력

7325189087
5
it
your
reality
real
our

예제 출력

2
reality
our

예제 입력 2

2285064252258219
5
long
false
cat
tail
black

예제 출력 2

0
No solution.

힌트

출처

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

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