The most tragic problem I've encountered since I started writing
This problem can only be solved by brute force pruning
Used prefix marking and diagonal marking to shorten speed
23 1
23 3
These two test cases cannot pass...
I had to compress the answer (the answer is very large, I used base 62) to pass
//====================================================================||
// ||
// ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%2d ",dp\[htx\]\[hty\]);}Pln();}
#define M 100005
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int seize\[M\];
int sall\[M\];
int mz\[10\]\[10\];
int s\[50\]\[M\];
char strnum\[M\]\[20\];
int snum\[50\],tl,sum;
vector<int\> spnum\[50\]\[3\]\[105\];
int head\[50\]\[M\];
int ls\[50\]\[10\]\[50\];
string ans\[1000\];
int nans;
int line\[10\];
int add(int x){
char str\[100\];
int ans=0;
sprintf(str,"%d",x);
int len=strlen(str);
for(int i=0;i<len;i++){
ans+=str\[i\]-'0';
}
return ans;
}
void pre(){
Set(seize,0);
Set(sall,0);
Set(snum,0);
Set(head,0);
Set(s,0);
for(int i=2;i<M;i++){
if(!seize\[i\]){
if(i>=10000){
int t=add(i);
sprintf(strnum\[i\],"%d",i);
s\[t\]\[snum\[t\]++\]=i;
for(int j=0;j<3;j++){
int k=(strnum\[i\]\[j\]-'0')\*10+(strnum\[i\]\[4-j\]-'0');
spnum\[t\]\[j\]\[k\].PB(i);
}
int tt=0,tt2=0;
for(int j=0;j<5;j++){
tt=tt\*10+strnum\[i\]\[j\]-'0';
tt2+=strnum\[i\]\[j\]-'0';
head\[t\]\[tt\]=1;
ls\[t\]\[j\]\[tt2\]=1;
}
}
for(int j=i+i;j<M;j+=i){
seize\[j\]=1;
}
}
}
}
bool first;
void dfs(int d1,int d2,int dep){
if(dep==5){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)ans\[nans\].PB(mz\[i\]\[j\]+'0');
}
nans++;
return ;
}
int k,j;
if(dep==0){
k=0;
j=(strnum\[d1\]\[0\]-'0')\*10+(strnum\[d2\]\[4\]-'0');
}
else if(dep==1){
k=1;
j=(strnum\[d1\]\[1\]-'0')\*10+(strnum\[d2\]\[3\]-'0');
}
else if(dep==2){
k=2;
j=(strnum\[d1\]\[2\]-'0')\*10+(strnum\[d2\]\[2\]-'0');
}else if(dep==3){
k=1;
j=(strnum\[d2\]\[1\]-'0')\*10+(strnum\[d1\]\[3\]-'0');
}
else if(dep==4){
k=0;
j=(strnum\[d2\]\[0\]-'0')\*10+(strnum\[d1\]\[4\]-'0');
}
int size=spnum\[sum\]\[k\]\[j\].size();
for(int i=0;i<size;i++){
int now=spnum\[sum\]\[k\]\[j\]\[i\];
// printf("%s\\n",strnum\[now\]);
for(int jj=0;jj<5;jj++){
mz\[dep\]\[jj\]=strnum\[now\]\[jj\]-'0';
}
bool canput=true;
for(int jj=0;jj<5;jj++){
int a=line\[jj\]\*10+mz\[dep\]\[jj\];
//printf("%d ",line\[jj\]);
if(!head\[sum\]\[a\]){
canput=false;
break;
}
}
if(canput){
for(int jj=0;jj<5;jj++)line\[jj\]=line\[jj\]\*10+mz\[dep\]\[jj\];
dfs(d1,d2,dep+1);
for(int jj=0;jj<5;jj++)line\[jj\]=line\[jj\]/10;
}
}
return ;
}
void xprint(int x){
vector<int\> f;
for(int i=x;i>0;i/=62){
f.PB(i%62);
}
for(int i=f.size()-1;i>=0;i--){
int t=f\[i\];
if(t<10)printf("%d",t);
else if(t<36)printf("%c",'A'+t-10);
else if(t<62)printf("%c",'a'+t-36);
}
}
void solve(){
nans=0;
for(int i=0;i<1000;i++)ans\[i\].clear();
int d1,d2;
for(int i=0;i<snum\[sum\];i++){
for(int j=0;j<snum\[sum\];j++){
if(strnum\[s\[sum\]\[i\]\[2\]==strnum\[s\[sum\]\[j\]\[2\]&&strnum\[s\[sum\]\[i\]\[0\]==tl+'0'){
d1=s\[sum\]\[i\];
d2=s\[sum\]\[j\];
//debug("%d %d\\n",d1,d2);
Set(line,0);
Set(mz,0);
dfs(d1,d2,0);
}
}
}
sort(ans,ans+nans);
for(int i=0;i<nans;i++){
int size=ans\[i\].size();
if(i)Pln();
for(int j=0;j<size;j++){
printf("%c",ans\[i\]\[j\]);
if(j%5==4)Pln();
}
}
/\*
for(int i=0;i<nans;i++){
int size=ans\[i\].size(),t=0;
for(int j=0;j<size;j++){
if(t<10000){
t=t\*10+ans\[i\]\[j\]-'0';
if(j==size-1){
xprint(t);
}
}else{
xprint(t);
t=ans\[i\]\[j\]-'0';
}
}
}\*/
}
void decode(char str\[\]){
int len=strlen(str);
int t=0;
int npn=0;
bool first=true;
for(int i=0;i<len;i++){
if(t<10000){
if(str\[i\]<='z'&&str\[i\]>='a')t=t\*62+str\[i\]-'a'+36;
else if(str\[i\]<='Z'&&str\[i\]>='A')t=t\*62+str\[i\]-'A'+10;
else t=t\*62+str\[i\]-'0';
}
if(t>=10000||i==len-1){
if(npn==0){
if(!first)Pln();
first=false;
}
printf("%d\\n",t);
npn=(npn+1)%5;
t=0;
}
}
}
struct{
int s,t;
char \*pref;
}fpre\[\]{
//{11,1,"2x53eL7t5Dq53Sj2x58dX7t53eL8fH3Sj3ON8P1D4B3T1"},
{23,1,"2xrJivGYxMFP4yh2xrOfDGYxHJ74yh36ZG7NI3rODL4yh3FHDWFPrFIpT51b3FHMYZH0XKYt36Z3GjMoXAC76UTNhz3GjOAjECLJoR51b3LxEsRJ9nIuhAAx3NPNjREUvF9r9iD3U5JivI0f6hXIYd3Y94YZJvzIMRK4h3Zt7BRGovD6hPmt3Zt9l7GovAX1Pmt3b3G7NMSlJH351b3b3H4tI2PJ8L8d93b3HTZLzjIEJ5BB3b3I3rJMrGfL8mj3bvKc5GkH6wvIYd3jlHfBEsR6UTNhz3mf7mbAX1NnDKaL3mfAMHAX1LDXKaL3mfF0rH4bAX1K4h3oPLtvH39Igl51b3oPOarDRbJeH4yh3pr53LNox7ynPmt3qRJrLGY560ZKDP3sBMiRIQnCm58gL3yHEzhMVfM2L2xr3yHFVdAYTFr7KaL3zjEzhJuXOc12xr41TDWFMFPLf751b41TFLl6utGK9NrZ4457QpMSlNt18d9445I0fIQnFmBAC744x8A7MIJLiJAE944xGHXOrzB4PAAx45pHVbG29K3F8n145pHpLIpTHZ58A745pOfDO1j53v8d945pPrF3jl91FNll46P76nLFHPrF8A746hEzh9VjE9jNhz489Ezh6ubGjPNhz49b3Y9CrJMCnNhz49bCA3ILZNBT8d94FhGzNChRODL8Jz4I1H7n8nJATpPmt4IbCQ1AC7Fr7Nhz4ItHVbGI7K3F8Jz4ItOAjA1fJoR8A74LD36ZPrF9SpNhz4MNDSBA1xK4hIYd4O7JW94LDEWNNhz4O7JW9EjR3yZNrZ4PHDfFH4tNAJ8A74PHNjRF0rF9r8AP4PHOGXEUvDat9iD4SlH4tKzJIyB4yh4SlKBxGYxMIJ2xr4WXDjtJuX9kFIYd4WXIK7FK1Jg18d94WXIa5Eo5Jvz8d94WXIgBEI9KLp8d94WXNXFEo5DR1AAx4WXNt1Eo5Ed38d94XzC8J9XTLhRIYd4YZH4tKyRIpT52T4ZRIK795tOpN9f14ZRIaxA7lNWf9f14aJAGTLQbM2L8A74aJMPrHJ7JCh2xr4bBMPrHJ73b3IYd4ijJuXH4tLnp2xr4ld7GfEsRFr7Nhz4ldKaLBPJKvX8n14r94yhAYBMEFNrZ4r955fB1DLnpNhz4r9JN9HZ567pIYd4sJCFZLnpO433U54yzGovCeFNrZ8A752TNXFEo5DR19f153vD6hO9HJ8L51b55N5cBO7XLQbAE955NG4TO7XAyJAE955NGWdO7XCZt8AP577MPrGnB3b3IYd5BB8ElKNZE7hIYd5BBGovEP7BVzIYd"},
{23,3,"8A7F7FE2BIyBAC78ETCaBOIZGK952T8ETMUDGWdEC352T8GnGQXH4bEzh9iD8GnIXBH4tCQ1AAx8GnIXBHapCQ19f18GnP3b45p3GjPmt8HfLzj4XzLzR9f18IF58Z9xJJNjNhz8IF9LZGWdBj3KaL8JhFSjBmXCMFIYd8JzA9nHXd6arNrZ8JzNS1BfHI3r4yh8OvMYZ67p8oBKaL8Q5HfBFmBK5r4WX8Q5I3r78XOXf8Jh8Q5I3rHXdE8Z8Jh8VJBO9Oc1Gzf4yh8VJEsRJ9nDi9AE98d9CrJ8g3G5vKDP8d9MEFFRHH4b36Z8g3BR3KNZGK99f18g3PrFBIvCMp8Gn8gL4qHO43K698n18kP7dbIa5LGjAF18kPCaBOIZGK94WX8kPMEFI2PEUv2xr8kPOqpCpHBmX8Gn8khCm5DxpMiR8Gn8khOAjHWB7P58d98mjLFHCeFE8Z9f18n1ILZChRI0f8d98n1KvFChRFQz8d98nb4hHOpNJMr8mj8nbAo9MYZJH352T8oB9LZG0hBj3KaL8oB9Lr7dbM7ZIYd8oBDNpPrFAGT8A78oBEY7Ao9Bj3KaL8oBGP5FFfHNl8d98oBL5hFFfBfH9f18oBNAJECvC1d8Gn8uZMIJBQlDe5AC78uZOrzBQlB4PAC78uZP5LHVb6ed8Jh8wJOarDi9EC352T8xTEjRIN1JN952l8xTFQz8IFNY7AF18xTI0f8IFKyRAF18xTIh3I2PB7t9f18xTO9HH0X6hX9f18xlM2d79hJX18mj91FEsRIdrDi9AE991FF0r4aJE8ZNir91FJrL8kh8d9KDP91FMR18kh63TKDP91FPMl4aJ3mfNir91FPrF3oP445Nir92h53vCalG0hNll92h8nbAF1EgXNhz92hA1xHU963TNrZ92hK7bGY5Byj8mj92zK7bGY5Cal8AP92zPGxGY57RP8AP95t4FhHXdBj3NrZ95t66NHapPWd8A795tBVhBvF8A7Pmt95tIXBFQz4r9IYd995CQ1HapIXB8mj9ApHsFAYBK5r8mj9Dj53LKwzMSl8n19DjOQh4KvPWd2xr9DjOpNAb5GnB52T9FBBO9PWdHDJ36Z9Fl3ZtKzJMTvAAx9Fl8g3KzJHNlAAx9G3ILZChRI0f8A79G3KvFChRFQz8A79G3Lt3A4Z6XxIiD9If4yhGFnBVzOQh9If76nG2jPrF8AP9IfCG9G2jKht8AP9IfG2jGovE8ZAAx9IfHWBG29Eq78mj9IfK5rG29CGR8mj9LZF9rJNjEJt8Gn9RN9bXFnd5qPPmt9V9HkzLeF9Fl8Jh9VjG5vH4bE8Z9f19VjHkzO436pN8Jh9VjHmRDyPGwT8Gn9XB3WzIdrOXfAE99XBDNpJvzEzh8d99XBEs9J9DE8Z8mj9XBG0hFFfHWB8A79YvK7bG29Cal8AP9YvNllBvFBVh9iD9YvPGxG297RP8AP9a59Lr6rhM7ZIYd9a5HmRDat6oDIiD9a5L5hETlBfH9f19bXHkzDfFHBH8Gn9bXNjR52l4O7Nhz9f1Jg1EI9IK74WX9f1PmtB2xBfH8Jh9kF4PHGzfBT5NrZ9kF82HJivNzh4yh9kF9YvGzNBT5IiD9kFDEpEWNNzh4yh9l7Av7O1jGkH51b9n930lIu7OarAAx9n933xIu7OXfAAx9n9AuFCaB9UHNhz9n9CKDJ9nM8j33x9n9Es9ItFE8Z8mj9n9HTZJ9nGzN33x9n9MPrDwfBXR8mj9n9MPrJ9D6Kt8mj9vrLTn5BBLFr8d99wRHNlETlGP58Gn9wRP5LGTj6ed8Jh9wj6qp7ArNnDIiD9xJBdpCMFDoFIiD9yBEGhDSBOGF4WX9yBLiJDi9G2j52TA0D82HJSxNzh4yhA0D8HfJvzK5r8A7A0DDEpEGPNzh4yhA1f8HfKzJHWB9f1A1fG0hKzJ9n99f1A1fJrLG29CEz8JhA1xLeF92h72jIiDA3P30lOrzJuX8d9A3P4FhGnBBVzNrZA3PCUf5yXDfFOHzA4ZAiLMUDK6936ZA4ZJrLG29CEz8GnAAxCQ1H4tIXB8GnAAxG7NO215yXAAxACh58ZIK7OXf8GnAGBAF18xlD9JNrZAGBMTv6B13GjOHzAGT2jLNtJOZ751bAGT7u9IQnOqp51bAGTFdBIQnH7n51bAJ58BZHmRBe7IYdAJ58WlI2PB2xIYdAJ5CKD9DjFubIiDAJ5CKDIdrM8j33xAJ5HTZIdrGzN33xAJ5K3F9Dj8BZIiDAJ5MCn6qp3FZNrZ"},
{25,6,"FubEsRMUD81P5BBFubHTZMEF5gF5BBFubK3F6cbIiD5BBFzp5OpLzjI3r51bFzp8kPCfz3GjPmtFzpIgl9n9CHt9iDG1HNtJ6g59f1AE9G1HNtJ7C19f19iDG1HOpN7BR9f18mjG29NTTCfz9Fl52TG2j5btCcnMUD9iDG2j5f5CcnMR19iDG2j8BZCcnJuX9iDG2j8ElCcnJrL9iDG2j9LZHTZ53LIYdG4T5hhH4b72jKaLG4T8mjJeHCG99iDG4TH4t4SlAJ5IYdG4TH4t52T9jNIYdG7NAYBECLFQzAAxG7ND7rECLCrJAAxG7NE0jGVlAAx9f1GFn35PH39JrLAE9GFn35PHZ5JrL9iDGFnK697d13mfIiDGHX5J1KADEY7AAxGK95OpDwNPmt51bGK97P5JNjEZr8n1GK9EMnDWFC1dAF1GK9PGx6cJ9wj8JhGLt2jLCMpOqpAAxGLtIK77DT401KaLGQXJZ3G5v9LZ52lGTj44NGY5JBXAC7GTjGI7J7l4LDAF1GVl35PGnBJrLAE9GVl35PHJ7JrL9iDGY5K4h5btJCh52TGY5NQZCfz8mj52TGYxJBXCMFACh8APGa73WzKADMiR3U5Ga78gLKADHZ53U5Ga7H4b3139DjKaLGa7JoR9FBC3N8mjGaP8mjJ8LCG99iDGaP995IiDBn7AF1GipEWNECvCkv8GnGjP489KADKvX4WXGjP489PMlFiz4WXGjP4bBJeHKyR4WXGjPCZt9BzJBX8n1GjPCrJ8Q5Jg18n1GjPI0f3jlJg18JzGjPI0fJLP44N8JzGjPLtvJbN33x5BBGjPLzj8APEP75BBGjPNtJ9FBBZT52TGkHG1HJeH3prAE9GnBCMp9iD3prNllGovDEpH399BzAAxGwTCrJ8g3Jg18JzGwTK7b9iDBQl8GnGwl489JoRMTv36ZGxLEI952T6TtNhzH39Bpj7RPLMp8mjH39LTnIuh3zj52TH39LjlIuh4Fh4WXH4b3U5PbHHM12xrH4bAYBHpLI3r2xrH4bHWBDR19f18n1H4bK5rDR175L8n1H4t5OpCcnNDD8A7H7n4a12zJI3rNirH9FBaLA1f3zjNirHCj49bJrLMIJ2xrHDJAer9IxJ7lAAxHJ7DxpMTv9l72xrHJ7Es9GY58xT8n1HJ7NtJ7Rz9f18APHM1Ao99FlKNZ8gLHM1JMr6pf4D5IiDHM1OHz9VjCG933xHNl4YZ2zJHpLNirHNl63THDJ7GfIYdHU95OpM2dGVl52THU9GovJJ544x8mjHV14YZ2jLHpLNrZHWB33xCeFOZ78gLHWB9VjIbpC3N8mjHWB9lzJ7lBn78GnHWBGYxKAD4458APHWBNY746PCcn8gLHXd9f1Av7JZ38n1HXdCrb8Ov3o7NrZHXdJ8LBtD97d8n1HZ5Es9GI78xT8n1HapNox4qHC3N8APHjX995JU7Bn78JzHpLDWFO437a73U5HsFBUFDPHFRH8GnHsFBaL9Fl3zjNllHsFDr9EUvByj8GnHzDIMR9IfB7J9iDHzDK3F6cb36ZIiDI0f30lFFNM2d8API0f33xFFNLzR8API0f33xOc1HJ73U5I0f46PECvLt38GnI0f92zG0h2p9KaLI0f9f1Av7JZ38JzI0fAer7TjLhR8d9I0fDWFOc16qp3U5I0fG5vFFN8xT8API2PAo9A1f3k3NrZI2PGYxJ7l4aJ8API3r2p9GK98gLKaLI3r5J1CfzLnp8d9I3r81PFoD401KaL"},
{25,8,"LA54dXF7rC8vJBrLBX9qfCWj8TbKDjLBXGpp53f96DK51LBXKglD8TCZd4frLBpJurJMJ77P4frLERHJj9jzJIF4frLERMD7FSl36tAF3LGB7dL7CdG55K51LGBGVD6wNHJRAF3LGBK6BEBnC594cxLHdKafD8TCZd4frLID3ybHFx95vKdZLJfNm5CanA3R4WHLQ34dXDq1C8vKDjLQ3MD7Cbf5gZAKrLQ3Mg97RjG5N4cxLU74c5Iv17A1K51Lgt3Zv9lRBR5PmvLhl8mBEDpHJRAF3LjnB8nAF34htOQjLkf9lRGx54bDJBrLkfIpDJKH7k14c5LlFJ7D44PMn74WHLupO89DrB7k14c5LvzO6hCbf3H3AKrLx9IRP7RjEhj9iFLybGSb9nTFCD8pNMD7Lhl3Zv4XjKDjMEH3ZvLjn44hKdZMEHB8DKiDEhR3U7MEHDEr9jzHKt9iFMEHIXnKf17lB33zMKNAcr8vB57RPGPMPJ5fPCbxLlF9oLMRLINLDkD7SJAF3MSnBOBB5tMn74WHMT54M7H194XjNsBMT54WHJNl6hHJBrMT5DPt4JDBx1K73MT5L0D3XJ58bK73Mg98jZGoxFCD8pNMg9AYn95vOnN581Mg9AYn9brOnN4c5MkD3ybJ7D6CnKDRMkDB8DKCHEhR3U7MlfDErNGR9vJ33zMlfNSdHnv5A333zMlx3qBGFX3ybPPzMlx4XjIs76sbJBrMlx4xrBot8pNNsBMlxAYn9brOnN4WHMlxO5FBc7AIp3U7Mor4HlBotEbvIipMvFFi99m1JEl4c5N1dDErCbxEbd8mBN1dIEdCbx9br8mBNG9B8n9U14bDNm5NGRIrFETnCan33z"},
{25,9,"Nm581j7iZN1d9iFNozDq1C59Hu14c5NozGPhC59FKL4c5NpH6fpC594G1PPzNrtBEbJtz70jAF3O1T5vNEvNMlx4c5OEFJBrCbf5tdAKrOH9DrBCLzBR5AKrOKv8evOat4KfAKrOKvBOB5alPoN581OQjB1XIpD7dvAKrOQjDZl9iX3tfKdZOVfAcr7R9JLjAKrOWXAcr7QH3tfPmvOWpEBnAIp4VzIipOXPDEHJYn57R9oLOat7z7CbfHML9iFOatBUZDPtCQ3AKrOatD8TCbfCCz9iFOatIYx4JD49dKdZOdnDJnJtz49dAF3OnNGFX4c5LyJ4cxOnNIvb4c5JIF4cxOtl8dT9m18JRKdZOtlAYn9vb6l3K73OtlBEbIs770jAF3Ou3Iv13Zv4mFK51Ou3JJh3H34XjKDjP1JIv14Lp4mFJBrPGPIs749vJHx4frPGPIs7JBr4G14frPGPJIFB6BBvZ4frPHHIs748l3t5K51PLL2rDFCnPmv33zPLL8nd4Xj9nTNm5PLdB3HGclEbd4cxPLdJJh32X4KfKDjPPzBc78jZ7IjJBrPPzIpD45r3qBK51PWx7z7CbfHML8mBPZr2o1KQnEo78dTPZr33z4JDDWHPmvPZr81jC8vHsH8dTPZrD9vJuZA7n3U7PoNKzL5cDFEF4c5"},
};
int main(){
ios\_base::sync\_with\_stdio(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w+",stdout);
pre();
int test;
scanf("%d",&test);
while(test--){
scanf("%d%d",&sum,&tl);
// printf("\\n%d %d\\n",sum,tl)a
bool fin=false;
for(int i=0;fpre\[i\].pref;i++){
if(fpre\[i\].s==sum&&fpre\[i\].t==tl){
fin=true;
decode(fpre\[i\].pref);
// printf("%d %d\\n",fpre\[i\].s,fpre\[i\].t);
//printf("%d %d\\n",sum,tl);
break;
}
}
Set(mz,0);
if(!fin)solve();
if(test)Pln();
}
}