P1092 [NOIP 2004 Senior] Cryptarithm

A cryptarithm is an arithmetic expression where some digits have been “eaten by worms,” and we must determine the missing digits from the remaining ones. Consider a simple example: $$\begin{aligned} \verb!43#9865#045! \\ +\qquad \verb!8468#6633! \\[-1em]\underline{\kern{8em}} \\ \verb!44445509678! \\ \end{aligned}$$ Here, the character `#` denotes a missing digit. From the equation, it is easy to see that the two missing digits in the first line are 5 and 3 respectively, and the missing digit in the second line is 5. Now we add two constraints to the problem: First, we only consider addition cryptarithms. The addition is in base $n$. The three numbers in the expression each have $n$ digits, and leading zeros are allowed. Second, all digits have been replaced by letters. We only know which digits are equal; equal digits are represented by the same letter, and different digits by different letters. If the addition is in base $n$, we use the first $n$ uppercase letters of the English alphabet to denote the $n$ distinct digits $0$ to $n - 1$; however, these $n$ letters do not necessarily represent $0$ to $n - 1$ in order. The input guarantees that each of the $n$ letters appears at least once. $$\begin{aligned} \verb!BADC! \\ +\quad \verb!CBDA! \\[-1em]\underline{\kern{4em}} \\ \verb!DCCC! \\ \end{aligned}$$ The above is a base-4 equation. Clearly, if we let $\verb!ABCD!$ represent 0123 respectively, the equation holds. Your task is: given a base-$n$ addition cryptarithm, determine which digits the $n$ different letters represent so that the addition holds. The input guarantees there is exactly one solution.

- The first line contains an integer $n$, the base. - The second to fourth lines each contain a string of uppercase letters, representing the two addends and the sum, respectively. These 3 strings have no spaces at either end, represent digits from high to low, and each has exactly $n$ characters.

Output one line with $n$ integers separated by spaces, representing the digits corresponding to $A, B, \dots$ in order.

Constraints: - For 30% of the testdata, $n \le 10$. - For 50% of the testdata, $n \le 15$. - For 100% of the testdata, $1 \le n \le 26$. Translated by ChatGPT 5