835 - Square of Primes

[Ghost77 dimen]

I can't figure out the sentence

"The solutions must be in ""ascending"" order"

in the context.

What is the meaning of the word "ascending" ?

Help me , thank you.

[Stefan Pochmann]

Don't they have dictionaries where you come from?

It means you show the smallest solution first, then the second smallest, ..., then the largest.

In this problem, two solutions are compared lexicographically line by line (if I remember correctly...).

[lowai]

There is a same problem on USACO Training site. My program can pass all data on the USACO Training Site, but got WA here. After getting WA for so many times, i use the standard code on the training site, and get WA as well. What's wrong?

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define MAXP 1000
#define MAXS 200

typedef struct {
int d[5];
int val;
} PRIME;

typedef struct {
int n, r[200];
} RECORD200;

typedef struct {
int n, r[50];
} RECORD50;

typedef struct {
int n, r[20];
} RECORD20;

typedef struct {
char s[5 * 5 + 1];
} SOLUTION;

PRIME p[MAXP];
int np;
int prime[10][10][10][10][10];
int dg_sum;
int sq_a,sq_b,sq_c,sq_d,sq_e,
sq_f,sq_g,sq_h,sq_i,sq_j,
sq_k,sq_l,sq_m,sq_n,sq_o,
sq_p,sq_q,sq_r,sq_s,sq_t,
sq_u,sq_v,sq_w,sq_x,sq_y;

RECORD200 pat1[10];
RECORD200 pat2[10];
RECORD50 pat3[10][10];
RECORD20 pat4[10][10][10];
RECORD20 pat7[10][10][10];
RECORD20 pat8[10][10][10];
SOLUTION sol[MAXS];

int nsolution;

void solution(void) {
sol[nsolution].s[0] = sq_a; sol[nsolution].s[1] = sq_b;
sol[nsolution].s[2] = sq_c; sol[nsolution].s[3] = sq_d;
sol[nsolution].s[4] = sq_e; sol[nsolution].s[5] = sq_f;
sol[nsolution].s[6] = sq_g; sol[nsolution].s[7] = sq_h;
sol[nsolution].s[8] = sq_i; sol[nsolution].s[9] = sq_j;
sol[nsolution].s[10] = sq_k;sol[nsolution].s[11] = sq_l;
sol[nsolution].s[12] = sq_m;sol[nsolution].s[13] = sq_n;
sol[nsolution].s[14] = sq_o;sol[nsolution].s[15] = sq_p;
sol[nsolution].s[16] = sq_q;sol[nsolution].s[17] = sq_r;
sol[nsolution].s[18] = sq_s;sol[nsolution].s[19] = sq_t;
sol[nsolution].s[20] = sq_u;sol[nsolution].s[21] = sq_v;
sol[nsolution].s[22] = sq_w;sol[nsolution].s[23] = sq_x;
sol[nsolution].s[24] = sq_y;sol[nsolution].s[25] = 0;
nsolution++;
}

void fill(void) {
int i,j,k,l,m,n,o,q, ii,ij,ik,il,im,in,io,iq,wi,wj,wk,wl,wm,wn,wo,wq;
ii = pat1[sq_a].n;
for (i = 0; i < ii; i++) {
wi = pat1[sq_a].r;
sq_g = p[wi].d[1];
sq_m = p[wi].d[2];
sq_s = p[wi].d[3];
sq_y = p[wi].d[4];
ij = pat2[sq_m].n;
for (j = 0; j < ij; j++) {
wj = pat2[sq_m].r[j];
sq_u = p[wj].d[0];
sq_q = p[wj].d[1];
sq_i = p[wj].d[3];
sq_e = p[wj].d[4];
ik = pat3[sq_a][sq_e].n;
for (k = 0; k < ik; k++) {
wk = pat3[sq_a][sq_e].r[k];
sq_b = p[wk].d[1];
sq_c = p[wk].d[2];
sq_d = p[wk].d[3];
il = pat4[sq_b][sq_g][sq_q].n;
for (l = 0; l < il; l++) {
wl = pat4[sq_b][sq_g][sq_q].r[l];
sq_l = p[wl].d[2];
sq_v = p[wl].d[4];
im = pat4[sq_d][sq_i][sq_s].n;
for (m = 0; m < im; m++) {
wm = pat4[sq_d][sq_i][sq_s].r[m];
sq_n = p[wm].d[2];
sq_x = p[wm].d[4];
sq_w = dg_sum - sq_u - sq_v - sq_x - sq_y;
if (sq_w != 1 && sq_w != 3 &&
sq_w != 7 && sq_w != 9)
continue;
if (prime[sq_u][sq_v][sq_w][sq_x][sq_y] == 0)
continue;
in = pat7[sq_c][sq_m][sq_w].n;
for (n = 0; n < in; n++) {
wn = pat7[sq_c][sq_m][sq_w].r[n];
sq_h = p[wn].d[1];
sq_r = p[wn].d[3];
io = pat8[sq_g][sq_h][sq_i].n;
for (o = 0; o < io; o++) {
wo = pat8[sq_g][sq_h][sq_i].r[o];
sq_f = p[wo].d[0];
sq_j = p[wo].d[4];
iq = pat8[sq_q][sq_r][sq_s].n;
for (q = 0; q < iq; q++) {
wq = pat8[sq_q][sq_r][sq_s].r[q];
sq_p = p[wq].d[0];
sq_t = p[wq].d[4];
sq_k = dg_sum - sq_a-sq_f-sq_p-sq_u;
if (sq_k < 0 || sq_k > 9)
continue;
sq_o = dg_sum - sq_e-sq_j-sq_t-sq_y;
if (sq_o != 1 && sq_o != 3
&& sq_o != 7 && sq_o != 9)
continue;
if (prime[sq_a][sq_f][sq_k][sq_p][sq_u])
if (prime[sq_k][sq_l][sq_m][sq_n][sq_o])
if (prime[sq_e][sq_j][sq_o][sq_t][sq_y])
solution();
}
}
}
}
}
}
}
}
}

int sol_cmp(const void *va, const void *vb) {
int i;
SOLUTION *sa = (SOLUTION*)va, *sb = (SOLUTION*)vb;
for (i = 0; i < 25; i++)
{ if (sa->s > sb->s) return 1;
if (sa->s < sb->s) return -1;
}
return 0;
}

int main()
{
int i, j, k, sum, d0, d1, d2, d3, d4, pp, rt, cases;

scanf("%d", &cases);
while (cases > 0) {
cases--;
scanf("%d %d", &dg_sum, &sq_a);

for (rt = (int)sqrt(99999), pp = 10008; pp < 99999; pp += 6)
for (i = pp - 1; i <= pp + 1; i += 2) {
j = i; sum = 0; k = 0;
while (j > 0) {
p[np].d[4 - k++] = j % 10;
sum += p[np].d[5 - k];
j /= 10;
}
if (sum != dg_sum) continue;
for (j = 5; j <= rt; j++)
if (i % j == 0) break;
if (j == rt+1) {
if (sum == dg_sum) {
d0 = p[np].d[0]; d1 = p[np].d[1]; d2 = p[np].d[2];
d3 = p[np].d[3]; d4 = p[np].d[4];
prime[d0][d1][d2][d3][d4] = 1;

pat1[d0].r[pat1[d0].n++] = np;
if (d0 == 1 || d0 == 3 || d0 == 7 || d0 == 9)
pat2[d2].r[pat2[d2].n++] = np;
if (d1 != 0 && d2 != 0 && d3 != 0)
pat3[d0][d4].r[pat3[d0][d4].n++] = np;
pat4[d0][d1][d3].r[pat4[d0][d1][d3].n++] = np;
pat7[d0][d2][d4].r[pat7[d0][d2][d4].n++] = np;
pat8[d1][d2][d3].r[pat8[d1][d2][d3].n++] = np;
p[np++].val = i;
}
}
}

fill();

qsort(&sol, nsolution, sizeof(SOLUTION), sol_cmp);
for (i = 0; i < nsolution; i++) {
for (j = 0; j < 5; j++) {
for (k = 0; k < 5; k++) printf("%d", sol.s[j * 5 + k]);
printf("\n");
}
printf("\n");
}
}

return 0;
}
[/cpp]

[bozhang@HIT]

Could anyone give me an example output for multicase input?
Suppose the input is :
3

11
1

1
1

11
1

[erdos]

Sample output for such input
11351
14033
30323
53201
13313

11351
33203
30323
14033
33311

13313
13043
32303
50231
13331


11351
14033
30323
53201
13313

11351
33203
30323
14033
33311

13313
13043
32303
50231
13331

[bozhang@HIT]

really thank you! I've got it.

[Moha]

I wrote this problem, with trie tree.
I created 45 tries, for each value in range 5..45. then I backtrack for each cell in grid,
for this, i use 12 pointers, for holding where am i in trie?
after setting a number in each cell, i go forward in each of 12 pointer.

But I think this method should be very very fast, because when i encounter a null pointer in just one of these pointers, i go back. and i always update 10,(and sometimes 12) pointers in each step.

can anybody help me?

[lighted]

In addition to xenon's observations:

- 5-digit primes end with digits 1, 3, 7, 9. So last row and column can have only digits: 1, 3, 7, 9.

- 5-digit primes cannot have leading zero. So first row and column don't contain digit 0.

I need help to avoid TLE. I don't want to send precalced answers.