암호산술 퍼즐
시간 제한5초메모리 제한512 MB
두 덧셈 단어가 주어졌을 때, 글자를 숫자로 바꾸어 식이 성립하는 해가 정확히 하나뿐인 사전 단어를 모두 찾습니다.
문제
암호산술은 문자에 숫자를 대입해 식을 성립시키는 퍼즐의 한 종류이다. Henry Dudeney가 1924년 7월호 Strand Magazine에 발표한 고전 예시는 다음과 같다.
이 퍼즐의 해는 다음 조건을 모두 만족하도록 문자에 0부터 9까지의 십진수를 대응시키는 것이다.
- 서로 다른 문자는 서로 다른 숫자를 나타낸다.
- 각 수의 첫 자리는 0이 아니다.
- 결과는 올바른 등식이어야 한다. 첫 두 수의 합이 세 번째 수와 같아야 한다.
고전 퍼즐의 유일한 해는 , , , , , , , 이며, 이때 가 성립한다.
좋은 퍼즐은 고전 퍼즐처럼 해가 하나뿐이다. 첫 두 단어가 주어졌을 때, 사전에 있는 단어 중에서 세 번째 단어가 되어 해가 유일한 좋은 퍼즐을 만드는 단어를 모두 찾아라.
입력
첫 번째 줄과 두 번째 줄에는 각각 한 단어가 주어진다. 이 두 단어가 덧셈의 두 항이다. 세 번째 줄에는 사전에 있는 단어의 개수 이 주어진다. 이어서 개의 줄에 사전 단어가 한 줄에 하나씩 주어진다. 사전 단어는 사전순으로 정렬되어 있다.
모든 단어는 2자 이상 15자 이하의 대문자로 이루어져 있다. 첫 번째 테스트를 제외한 모든 테스트는 같은 사전을 사용한다. 이 사전은 279,496개 단어를 수록한 Collins Scrabble Words (2019)이다. 첫 두 단어도 이 사전에 들어 있다.
출력
첫 줄에 주어진 두 단어와 함께 좋은 퍼즐을 만드는 사전 단어의 개수 을 출력한다. 다음 개의 줄에는 그러한 단어를 사전에 나온 순서대로 한 줄에 하나씩 출력한다.