[USACO] 1.3 Prime Cryptarithm(Winning Solutions)

주어진 n이 10이기 때문에 O(n^5)이어도 시한제약에 걸리지 않았다. n이 충분히 작다면 단순하게 푸는 것도 이기는 방법이 될 수 있다.

bool check_ok(int x, vector<int> &d)
{
    while(x)
    {
        int a = x % 10;
        if( find(ALL(d), a) == d.end() ) return false;
        x /= 10;
    }
    return true;
}

int main() {

    ofstream fout ("crypt1.out");
    ifstream fin ("crypt1.in");
   
    int n;
    fin >> n;
    vector<int> d;
    REP(i, n)
    {
        int a;
        fin >> a;
        d.pb(a);
    }

    int f1 = 0, f2 = 0, ret = 0;

    REP(i, d.size())
    {
        REP(j, d.size())
        {
            REP(k, d.size())
            {
                REP(l, d.size())
                {
                    REP(m, d.size())
                    {
                        f1 = d[i] + 10 * d[j] + 100*d[k];
                        f2 = d[l] + 10 * d[m];   
                        int p1 = f1 * (f2%10);
                        int p2 = f1 * (f2/10);
                        int p3 = p1 + 10*p2;
                        if( (p1/1000 == 0) && check_ok(p1, d) && (p2/1000 == 0) && check_ok(p2, d) && (p3/10000 == 0) && check_ok(p3, d))
                            ret++;
                    }
                }
            }
        }
    }
   
    fout << ret << endl;
    return 0;
}