Bài 3: Ghép số
Cay cú vì lần trước không giải được bài toán của Tèo đưa ra. Trạng Tí quyết ăn thua đủ với Tèo bằng cách đấu trí. Lần này nhờ sự trợ giúp của công nghệ nên Trạng Tí bèn mò lên Google tìm một bài toán cực khó mang hơi thở của tin học để đố Tèo. Bài toán như sau:
Cho N số A1, A2, … An khác nhau (0<A<=9). Hãy ghép N số này để được một số là số nguyên tố.
Dữ liệu vào: Là file văn bản có tên ghepso.inp có cấu trúc như sau:
- Dòng đầu tiên ghi số nguyên N (2<=N<=6)
- Dòng tiếp theo ghi N số khác nhau: A1, A2, … An (các số nhập cách trống)
Kết quả: Ghi ra file ghepso.out là các số nguyên tố ghép được. Mỗi số ghi trên một dòng và theo thứ tự từ nhỏ đến lớn. Nếu không ghép được số nguyên tố nào thì ghi ra kết quả là -1
Lần này lại đến lượt Tèo vò đầu bứt tai không thể giải nổi bài toán này và đành cầu cứu tới các bạn thi học sinh giỏi môn tin học lớp 9 huyện Thanh Chương. Mong các bạn giải bài này giúp Tèo với nhé.
Ví dụ:
ghepso.inp | ghepso.out |
2 1 3 | 13 31 |
2 2 4 | -1 |
Giải thích: Test đầu tiên có 2 số (1 3) ta có 2 cách ghép thành số 13 và 31 đều là số nguyên tố. Ở test thứ 2 có 2 số (2 4) ta cũng có 2 cách ghép tạo thành 2 số 24 và 42 nhưng chúng đều không phải số nguyên tố nên có đáp án là -1
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const ll maxn = 1e7+4;
const int m=1e9+7;
int n,a[15],x[100],kt=-1;
int check(int n)
{
if(n<2) return 0;
for(int i=2;i<=sqrt(n);i++) if(n%i==0) return 0;
return 1;
}
void Try(int i,int sum)
{
if(i==n)
{
if(check(sum))
{
cout<<sum<<"\n";
kt=1;
}
return;
}
for(int t=1;t<=n;t++)
{
if(x[a[t]]==0)
{
x[a[t]]=1;
Try(i+1,sum*10+a[t]);
x[a[t]]=0;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
freopen("GHEPSO.INP","r",stdin);
freopen("GHEPSO.OUT","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
Try(0,0);
if(kt==-1) cout<<"-1\n";
}
code đệ quy - quay lui đây nhé bạn
