NOIP '04 P4 - Bugs Eating Computation

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

The so-called "insect-eating calculation" means that part of the original calculation formula was eaten by insects, and we need to compute the missing letters based on the remaining numbers. Let's look at a simple example:

\displaystyle 43\#98650\#45+8468\#6633=44445506978

The character # represents the number was eaten by the insects. According to the formula, we can easily conclude: the two numbers in the first summand are 5 and 3, respectively, and the number in the second summand is 5.

Now, we make two constraints on the problem:

First, we only consider the insect-eating calculation of addition. The addition here is addition in base N, and the three numbers in the formula have exactly N digits, and leading 0s are allowed.

Secondly, the insects have eaten up all the numbers. We only know which numbers are the same. We represent the same numbers with the same letters and different numbers with different letters. If the formula is in base N, we take the first N capital letters of the English alphabet to represent the N different numbers from 0 to N-1 in the formula: but it is not always the case that A corresponds to 0, B corresponds to 1, etc. The input data guarantees that each of the N letters appears at least once.

\displaystyle BADC+CBDA=DCCC

The above formula is a formula in base 4. Obviously, as long as we let A,B,C,D represent 0, 1, 2, 3, respectively, the equality holds. Your task is, for a given addition formula in base N, to find the numbers represented by N different letters so that the addition formula is established. The input data is guaranteed to have exactly one solution.

Input Specification

The first line of the input contains a positive integer N (N \le 26). In the following three lines, each line consists of a string of upper-case English letters denoting the summands and the sum. There are no spaces on the left or on the right of the string. The numbers are given from the most significant bit (on the left) to the least significant bit. The lengths of the 3 strings are exactly N.

Output Specification

Output a line denoting the correspondence between the letters and digits: you should output N integers separated by a single space denoting the digits corresponding to A, B, C, \dots.

Sample Input

    5
    ABCED
    BDACE
    EBBAA

Sample Output

    1 0 3 4 2

Constraints

  • For 30\% of test cases, n \le 10.
  • For 50\% of test cases, n \le 15.
  • For all test cases, n \le 26.

Comments

There are no comments at the moment.