Submission #500895

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,0,-1,1,-1,-1,1};
const int dy[]={0,1,-1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fr first
#define sc second
#define reps(i,j,k) for(int i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> Pii;
typedef pair<int,vi > P;
typedef long long ll;

bool isPrime(ll n){
    for(ll i = 2; i * i <= n; ++i){
        if(n % i == 0)return false;
    }
    return n != 1;
}

ll convert(string a){
    return atoll(a.c_str());
}

void solve(string str,int depth,int bit){
    if(depth == str.size()){
        if(isPrime(convert(str))){
            cout << str << "\n";
            exit(0);
        }
        return ;
    }
    string copy = str;
    char x = str[depth];
    if(isdigit(x)){
        solve(str,depth+1,bit);
    }
    else{
        string num = "13579";
        rep(j,5){
            if(1&(bit>>j))continue;
            str = copy;
            rep(i,str.size()){
                if(str[i] == x){
                    str[i] = num[j];
                }
            }
            solve(str,depth+1,bit|(1<<j));
        }
    }
    return ;
}

int main(){

    string str;
    cin >> str;

    solve(str,0,0);
    cout << "-1" << "\n";
    return 0;
}

Submission Info

Judge Result