TTPC2015 D 文字列と素数

2015/09/28 (Mon) AtCoder TTPC 探索

問題

日本語

方針

アルファベットと数字の割り当てを全探索する． 割り当て方が高々 $5!$，素数判定に高々 $\sqrt{10^{10}}$ なので間に合う．

実装

vector<int> EratosthenesSieve(int n){
    vector<int> ps(n+1);
    range(i,2,n+1) ps[i] = i;
    for (int i = 2; i*i <= n; ++i)
        if (ps[i])
            for (int j = i*i; j <= n; j+=i)
                ps[j] = 0;
    ps.erase(remove(all(ps),0), ps.end());
    return ps;
}

bool isprime(ll n){
    static vector<int> ps = EratosthenesSieve(sqrt(1e10+1e4));
    rep(i,ps.size()){
        if(ps[i]*ps[i] > n) break;
        if(n%ps[i]==0) return false;
    }
    return true;
}

string s;
int n;
vector<char> cs;
int trans[256];
bool used[256];

ll dfs(int k){
    if(k == (int)cs.size()){
        ll x = 0;
        rep(i,s.size()) x = x*10 + trans[(int)s[i]]-'0';
        return isprime(x) ? x : -1;
    }
    for(char i : {'1','3','5','7','9'}){
        if(used[(int)i]) continue;
        used[(int)i] = true;
        trans[(int)cs[k]] = i;
        ll r = dfs(k+1);
        used[(int)i] = false;
        if(r != -1) return r;
    }
    return -1;
}

ll solve(){
    if((int)s.size() == 1) return 3;
    cs = vector<char>(all(s));
    uniq(cs);
    rep(i,256) used[i] = false;
    return dfs(0);
}

int main(){
    while(cin >> s){
        n = s.size();
        cout << solve() << endl;
    }
}