1 solutions
-
1
爆搜,调炸了,三天才过。
#include<bits/stdc++.h> using namespace std; #define ll long long ll a[6][6],k; bool vis[100000]; bool flag=true; priority_queue<string,vector<string>,greater<string> > ans; void print(); void dfs8(){ a[4][5]=k-a[4][1]-a[4][2]-a[4][3]-a[4][4]; if(a[4][5]>=0&&a[4][5]<=9){ if(vis[a[4][1]*10000+a[4][2]*1000+a[4][3]*100+a[4][4]*10+a[4][5]]){ a[5][4]=k-a[5][1]-a[5][2]-a[5][3]-a[5][5]; if(a[5][4]>=0&&a[5][4]<=9){ if(vis[a[5][1]*10000+a[5][2]*1000+a[5][3]*100+a[5][4]*10+a[5][5]]){ a[3][4]=k-a[1][4]-a[2][4]-a[4][4]-a[5][4]; if(a[3][4]>=0&&a[3][4]<=9){ if(vis[a[1][4]*10000+a[2][4]*1000+a[3][4]*100+a[4][4]*10+a[5][4]]){ ll t1=k-a[3][1]-a[3][2]-a[3][3]-a[3][4],t2=k-a[1][5]-a[2][5]-a[4][5]-a[5][5]; if(t1==t2&&t1>=0&&t2<=9){ a[3][5]=t1; if(vis[a[1][5]*10000+a[2][5]*1000+a[3][5]*100+a[4][5]*10+a[5][5]]){ if(vis[a[3][1]*10000+a[3][2]*1000+a[3][3]*100+a[3][4]*10+a[3][5]]){ print(); } } } } } } } } } } void dfs7(){ for(ll i=0;i<=k-a[1][3]-a[2][3]-a[3][3]&&i<=9;i++){ a[4][3]=i; a[5][3]=k-a[1][3]-a[2][3]-a[3][3]-a[4][3]; if(a[5][3]>9) continue; if(vis[a[1][3]*10000+a[2][3]*1000+a[3][3]*100+a[4][3]*10+a[5][3]]) dfs8(); } } void dfs6(){ for(ll i=0;i<=k-a[1][2]-a[2][2]-a[4][2]&&i<=9;i++){ a[3][2]=i; a[5][2]=k-a[1][2]-a[2][2]-a[3][2]-a[4][2]; if(a[5][2]>9) continue; if(vis[a[1][2]*10000+a[2][2]*1000+a[3][2]*100+a[4][2]*10+a[5][2]]) dfs7(); } } void dfs5(){ for(ll i=0;i<=k-a[2][1]-a[2][2]-a[2][4]&&i<=9;i++){ a[2][3]=i; a[2][5]=k-a[2][1]-a[2][2]-a[2][3]-a[2][4]; if(a[2][5]>9) continue; if(vis[a[2][1]*10000+a[2][2]*1000+a[2][3]*100+a[2][4]*10+a[2][5]]) dfs6(); } } void dfs4(){ for(ll i=0;i<=k-a[5][1]-a[3][3]-a[1][5]&&i<=9;i++){ a[4][2]=i; a[2][4]=k-a[5][1]-a[4][2]-a[3][3]-a[1][5]; if(a[2][4]>9) continue; if(vis[a[5][1]*10000+a[4][2]*1000+a[3][3]*100+a[2][4]*10+a[1][5]]) dfs5(); } } void dfs3(){ for(ll i=1;i<=k-a[1][1]&&i<=9;i++){ a[2][1]=i; for(ll j=1;j<=k-a[1][1]-a[2][1]&&j<=9;j++){ a[3][1]=j; for(ll kk=1;kk<=k-a[1][1]-a[2][1]-a[3][1]&&kk<=9;kk++){ a[4][1]=kk; a[5][1]=k-a[1][1]-a[2][1]-a[3][1]-a[4][1]; if(a[5][1]>9) continue; if(vis[a[1][1]*10000+a[2][1]*1000+a[3][1]*100+a[4][1]*10+a[5][1]]){ dfs4(); } } } } } void dfs2(){ for(ll i=1;i<=k-a[1][1]&&i<=9;i++){ a[1][2]=i; for(ll j=1;j<=k-a[1][1]-a[1][2]&&j<=9;j++){ a[1][3]=j; for(ll kk=1;kk<=k-a[1][1]-a[1][2]-a[1][3]&&kk<=9;kk++){ a[1][4]=kk; a[1][5]=k-a[1][1]-a[1][2]-a[1][3]-a[1][4]; if(a[1][5]>9) continue; if(vis[a[1][1]*10000+a[1][2]*1000+a[1][3]*100+a[1][4]*10+a[1][5]]){ dfs3(); } } } } } void dfs1(){ for(ll i=0;i<=k-a[1][1]&&i<=9;i++){ a[2][2]=i; for(ll j=0;j<=k-a[1][1]-a[2][2]&&j<=9;j++){ a[3][3]=j; for(ll kk=0;kk<=k-a[1][1]-a[2][2]-a[3][3]&&kk<=9;kk++){ a[4][4]=kk; a[5][5]=k-a[1][1]-a[2][2]-a[3][3]-a[4][4]; if(a[5][5]>9) continue; if(vis[a[1][1]*10000+a[2][2]*1000+a[3][3]*100+a[4][4]*10+a[5][5]]){ dfs2(); } } } } } int main(){ for(ll i=2;i<=99999;i++) vis[i]=true; for(ll i=2;i<=99999;i++) if(vis[i]) for(ll j=i;j*i<=99999;j++) vis[i*j]=false; scanf("%lld %lld",&k,&a[1][1]); if(a[1][1]==0){ printf("NONE"); return 0; } dfs1(); if(flag) printf("NONE"); else{ while(!ans.empty()){ for(ll i=1;i<=5;i++){ for(ll j=1;j<=5;j++) printf("%c",ans.top()[(i-1)*5+(j-1)]); printf("\n"); } printf("\n"); ans.pop(); } } return 0; } void print(){ string s=""; flag=false; for(ll i=1;i<=5;i++) for(ll j=1;j<=5;j++) s=s+char(a[i][j]+'0'); ans.push(s); }
- 1
Information
- ID
- 26
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 9
- Tags
- # Submissions
- 16
- Accepted
- 2
- Uploaded By