Problem 1.4.5 Prime Cryptarithm

출처: https://train.usaco.org/usacogate

---

문제 설명

A cryptarithm is usually presented as a pencil-and-paper task in which the solver is required to substitute a digit for each of the asterisks (or, often, letters) in the manual evaluation of an arithmetic term or expression so that the consistent application of the digits results in a proper expression. A classic example is this cryptarithm, shown with its unique solution:

    SEND           9567       S->9 E->5 N->6 D->7

+ MORE       + 1085        M->1 O->0 R->8

   -------           -------

 MONEY          10652      Y->2

The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. Since the asterisks are generic, any digit from the input set can be used for any of the asterisks; any digit may be duplicated as many times as desired.

Consider using the set {2,3,5,7} for the cryptarithm below:

 * * *

 x * *

 -------

 * * * <-- partial product 1 -- MUST BE 3 DIGITS LONG

* * * <-- partial product 2 -- MUST BE 3 DIGITS LONG

-------

* * * *

Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.

입력

Line 1:N, the number of digits that will be used

Line 2:N space separated non-zero digits with which to solve the cryptarithm

출력 

A single line with the total number of solutions. Here is the one and only solution for the sample input:

입력 예

5

2 3 4 6 8

출력 예

1

---

문제 풀이 내용

입력받은 수들을 set에 정리하고, 임의로 3자리수, 2자리수를 만들어서 계산을 했다. 그래서, 나오는 수들이 모두 집합에 있는지 확인해서, 있으면 (aaa, bb)를 기록해서 출력한다.

프로그램 내용

set <int> num_sets;

/// check all digit in sets
bool check_set(int input) ;

int main() {
    vector <int> used_nums;
    vector <int> aaa; /// a1a2a3
    vector <int> bb; /// b1b2b3

    /// reading used numbers
    for(int idx=0; idx < num_used; ++idx)
    {
    }

    sort(used_nums.begin(),used_nums.end()); 

    /// build aaa & bb
    for(int idx=0; idx < num_used ; ++idx)
    {
        for(int idx2=0; idx2 < num_used ; ++idx2)
        {
            for(int idx3=0; idx3 < num_used ; ++idx3)
            {
                aaa.push_back(100*used_nums[idx]+10*used_nums[idx2]+used_nums[idx3]);
            }
            bb.push_back(10*used_nums[idx]+used_nums[idx2]);
        }
    }

    vector <pair <int, int>> filtered;
    for(int idx=0; idx < aaa.size(); ++idx)
    {
        for(int idx2=0;idx2 < bb.size(); ++idx2)
        {
            int ccc = aaa[idx] * (bb[idx2]%10);
            int ddd = aaa[idx] * (bb[idx2]-(bb[idx2]%10))/10;
            int eee = aaa[idx] * bb[idx2];

            if ( ccc < 1000 && ddd < 1000 && eee < 10000)
            {
                if (check_set(ccc) && check_set(ddd) && check_set(eee))
                {
                    filtered.push_back(make_pair(aaa[idx], bb[idx2]));
                }
            }
        }
    }

    fout << filtered.size() << endl;

 

Chapter 1. Getting started