Page 2 of 2

Posted: Sat Oct 12, 2002 2:35 pm
by 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. :wink:

Posted: Sat Oct 12, 2002 4:47 pm
by 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...).

Posted: Sun Nov 03, 2002 7:16 am
by 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]

Posted: Thu Aug 07, 2003 3:41 am
by bozhang@HIT
Could anyone give me an example output for multicase input?
Suppose the input is :
3

11
1

1
1

11
1

Output example

Posted: Sun Aug 10, 2003 2:45 am
by 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

Posted: Mon Aug 11, 2003 4:58 am
by bozhang@HIT
really thank you! I've got it. :D

TLE

Posted: Tue Dec 13, 2005 4:37 pm
by 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?

Re: 835 - Square of Primes

Posted: Sun Nov 16, 2014 2:23 pm
by 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.