問題
数字の文字列が与えられる。
そこから全ての数字を好きに組み合わせて、３つの素数を作る。
３つの素数が複数通り作れるのであれば、その積が最も小さいものを返す。
解き方
数字の数は最大８つなので、全探索で解くことができる。
すべての数字のpermutationに対し、全ての区切りで３つの数を作り、それが全て素数であるか判定すればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PrimeAnagrams {
public:
bool isprime(int x){
if(x==2)return true;
if(x==1||x%2==0)return false;
for(int i=3;i*i<=x;i+=2)if(x%i==0)return false;
return true;
}
int calc(vector<int> num,int start,int end){
int x=0,p=1;
for(int i=end;i>=start;i--){
x+=p*num[i];
p*=10;
}
return x;
}
vector<int> primes(string anagram) {
vector<int> num,ans;
int n=anagram.size();
FORE(i,0,n)num.push_back(anagram[i]-'0');
sort(all(num));
do{
FORE(i,1,n){
FORE(j,i+1,n){
if(num[0]==0||num[i]==0||num[j]==0)continue;
int a=calc(num,0,i-1);
int b=calc(num,i,j-1);
int c=calc(num,j,n-1);
if(isprime(a)&&isprime(b)&&isprime(c)){
vector<int> tmp(3);
tmp[0]=a,tmp[1]=b,tmp[2]=c;
sort(all(tmp));
if(ans.size()==0||tmp[0]*tmp[1]*tmp[2]<ans[0]*ans[1]*ans[2])ans=tmp;
}
}
}
}while(next_permutation(all(num)));
return ans;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PrimeAnagrams {
public:
bool isprime(int x){
if(x==2)return true;
if(x==1||x%2==0)return false;
for(int i=3;i*i<=x;i+=2)if(x%i==0)return false;
return true;
}
int calc(vector<int> num,int start,int end){
int x=0,p=1;
for(int i=end;i>=start;i--){
x+=p*num[i];
p*=10;
}
return x;
}
vector<int> primes(string anagram) {
vector<int> num,ans;
int n=anagram.size();
FORE(i,0,n)num.push_back(anagram[i]-'0');
sort(all(num));
do{
FORE(i,1,n){
FORE(j,i+1,n){
if(num[0]==0||num[i]==0||num[j]==0)continue;
int a=calc(num,0,i-1);
int b=calc(num,i,j-1);
int c=calc(num,j,n-1);
if(isprime(a)&&isprime(b)&&isprime(c)){
vector<int> tmp(3);
tmp[0]=a,tmp[1]=b,tmp[2]=c;
sort(all(tmp));
if(ans.size()==0||tmp[0]*tmp[1]*tmp[2]<ans[0]*ans[1]*ans[2])ans=tmp;
}
}
}
}while(next_permutation(all(num)));
return ans;
}
};