Stuff

/*ID: rodrigo7PROG: prime3LANG: C++*/#include <iostream>#include <fstream>#include <string>#include <vector>#include <algorithm>#include <cassert>#include <iterator>#include <cstring>using namespace std;template <class T>ostream&operator<< (ostream &out, const vector <T, allocator<T> > &v){    typedef ostream_iterator<T, char, char_traits<char> > Iter;    copy (v.begin(), v.end(), Iter (out, " "));    return out;}ifstream fin ("prime3.in");#ifdef USACOLOCAL#define fout cout#elseofstream fout ("prime3.out");#define cout fout#endifint sum;int topleft;int square[5][5];bool none_so_far = true;int nprimes = 0;int primes[10000];char pdigs[10000][5];bool isprime[100000];bool first[5][10000];bool last [5][10000];bool efirst[5][10000];bool elast [5][10000];char givenlen[4][1000];char given[4][1000][10];int digsum(int);int col(int c, int len){    int ans = 0;    for (int i=0; i<len; i++)        ans = (ans * 10) + square[i][c];    return ans;}int getrow(int r){    int ans = 0;    for (int i=0; i<5; i++)        ans = (ans * 10) + square[r][i];    return ans;}int diag1(int len){    int ans = 0;    for (int i=0; i<len; i++)        ans = ans * 10 + square[i][i];    return ans;}int diag2(int len){    int ans = 0;    for (int i=len-1; i>=0; i--)        ans = ans * 10 + square[i][4-i];    return ans;}void search(int row, int cs[], int d1, int d2){#if 0    for (int r=0; r<5; r++)    {        cout << string (row, ' ');        for (int c=0; c<5; c++)            cout << square[r][c];        cout << endl;    }    for (int i=0;i<5;i++) cout << cs[i] << " ";    cout << d1 << " " << d2 << endl;#endif    /* pruning */    if (row == 1)    {        if (square[0][0] != topleft)            return;    }    /* termination checking */    if (row == 5)    {        /* woohoo */        if (!none_so_far)            fout << endl;        none_so_far = false;        for (int r=0; r<5; r++)        {            for (int c=0; c<5; c++)                fout << square[r][c];            fout << endl;        }        return;    }    int new_cs[5];    int d2mult=1;    for (int i=0; i<row; i++)        d2mult *= 10;#define DO_SEARCH do { \    int new_d1, new_d2; \    new_d1 = d1*10+square[row][row];\    if (!first[row+1][new_d1]) break; \    new_d2 = d2mult*square[row][4-row]+d2;\    if (!last[row+1][new_d2]) break; \    search(row+1, new_cs, new_d1, new_d2); \} while (0)     /* fill in row */        if (row < 2)    {        for (int i=0; i<nprimes; i++)        {            //int divisor = 10000;            for (int c=0; c<5; c++)            {                //square[row][c] = (primes[i]/divisor) % 10;                square[row][c] = pdigs[i][c];                new_cs[c] = cs[c]*10 + square[row][c];                if (c == 4 && !efirst[row+1][new_cs[c]]) goto nextpos1;                if (c != 4 && !first[row+1][new_cs[c]]) goto nextpos1;                //divisor /= 10;            }            //cout << string (row, ' ') << "inserted " << primes[i] << endl;            DO_SEARCH;nextpos1:;        }    }    else if (row == 2)    {        int new_d1, new_d2;        for (int i0=0; i0<givenlen[row][cs[0]]; i0++)        {int dig1=given[row][cs[0]][i0]; if (!first[1][dig1]) continue;            square[row][0] = given[row][cs[0]][i0];        for (int i1=0; i1<givenlen[row][cs[1]]; i1++)        {int dig2=dig1*10+given[row][cs[1]][i1]; if (!first[2][dig2]) continue;            square[row][1] = given[row][cs[1]][i1];        for (int i2=0; i2<givenlen[row][cs[2]]; i2++)        {int dig3=dig2*10+given[row][cs[2]][i2]; if (!first[3][dig3]) continue;            square[row][2] = given[row][cs[2]][i2];            new_d1 = d1*10+square[row][row];            if (!first[row+1][new_d1]) continue;            new_d2 = d2mult*square[row][4-row]+d2;            if (!last[row+1][new_d2]) continue;        for (int i3=0; i3<givenlen[row][cs[3]]; i3++)        {int dig4=dig3*10+given[row][cs[3]][i3]; if (!first[4][dig4]) continue;            square[row][3] = given[row][cs[3]][i3];            square[row][4] = sum-digsum(dig4);            // int dig5=dig4*10+square[row][4]; if(!isprime[dig5]) continue;            for (int c=0; c<5; c++) new_cs[c]=cs[c]*10+square[row][c];            if (efirst[row+1][new_cs[4]])            search(row+1, new_cs, new_d1, new_d2);        }}}}    }    else if (row == 3)    {        int new_d1, new_d2;        for (int i0=0; i0<givenlen[row][cs[0]]; i0++)        {int dig1=given[row][cs[0]][i0]; if (!first[1][dig1]) continue;            square[row][0] = given[row][cs[0]][i0];            square[4][0] = sum-square[3][0]-square[2][0]-square[1][0]-square[0][0];            square[3][1] = sum-square[4][0]-square[2][2]-square[1][3]-square[0][4];            new_d2 = d2mult*square[3][1] + d2;            if (!last[4][new_d2]) continue;            int dig2=dig1*10+square[3][1];            if (!first[2][dig2]) continue;            if (!first[4][cs[1]*10 + square[3][1]]) continue;            square[4][1] = sum-square[3][1]-square[2][1]-square[1][1]-square[0][1];            int bot2 = 10 * square[4][0] + square[4][1];            if (!first[2][bot2]) continue;        for (int i2=0; i2<givenlen[row][cs[2]]; i2++)        {int dig3=dig2*10+given[row][cs[2]][i2]; if (!first[3][dig3]) continue;            square[row][2] = given[row][cs[2]][i2];            square[4][2] = sum-square[3][2]-square[2][2]-square[1][2]-square[0][2];            int bot3 = 10*bot2 + square[4][2];            if(!first[3][bot3]) continue;        for (int i3=0; i3<givenlen[row][cs[3]]; i3++)        {            square[3][3] = given[row][cs[3]][i3];            int dig4 = 10*dig3 + square[3][3];            if (!first[4][dig4]) continue;            new_d1 = 10*d1+square[3][3];            if (!first[4][new_d1]) continue;            square[3][4] = sum-square[3][3]-square[3][2]-square[3][1]-square[3][0];            if (!first[4][cs[4]*10 + square[3][4]]) continue;            square[4][4] = sum-square[3][3]-square[2][2]-square[1][1]-square[0][0];            square[4][3] = sum-square[3][3]-square[2][3]-square[1][3]-square[0][3];            int bot5 = 100*bot3 + 10*square[4][3] + square[4][4];            if (!isprime[bot5]) continue;            search(5, cs, 0, 0);        }}}    }    else if (row == 4)    {        for (int c=0; c<5; c++)        {            square[row][c] = sum;            for (int r=0; r<row; r++)                square[row][c] -= square[r][c];        }        //cout << string(row, ' ') << "trying " << getrow(4) << " = ";        //for (int i=0; i<5; i++)        //    cout << square[4][i];        //cout << endl;        //for (int c=0; c<5; c++) new_cs[c]=cs[c]*10+square[row][c];        if (isprime[getrow(4)]                && isprime[d1*10+square[4][4]]                && isprime[d2mult*square[4][0]+d2])            search(5, cs, 0, 0);    }}int digsum(int n){    int ds=0;    while (n > 0)    {        ds += n%10;        n /= 10;    }    return ds;}void given_ins(char *len_p, char *xs, int x){    for (int i=0; i<*len_p; i++)        if (xs[i] == x)            return;    xs[(*len_p)++] = x;}int main(){	fin >> sum >> topleft;    bzero(isprime, sizeof(isprime));    bzero(last, sizeof(last));    bzero(first, sizeof(first));    bzero(efirst, sizeof(efirst));    bzero(givenlen, sizeof(givenlen));    bzero(given, sizeof(given));    for (int i=10001; i<100000; i+=2)    {        bool prime = true;        for (int j=3; j*j<=i; j+=2)            if (i % j == 0)            {                prime = false;                break;            }        if (prime && digsum(i) == sum)        {            int t = i;            bool canend = true;            for (int d=4; d>=0; d--)            {                if (t % 10 == 2 || t % 10 == 5) canend = false;                pdigs[nprimes][d] = t % 10;                t /= 10;            }            primes[nprimes++] = i;            first[1][i/10000] = true;            last[1][i % 10] = true;            first[2][i/1000] = true;            last[2][i % 100] = true;            first[3][i/100] = true;            last[3][i % 1000] = true;            first[4][i/10] = true;            last[4][i % 10000] = true;            isprime[i] = true;            if (canend)            {                efirst[1][i/10000] = true;                elast[1][i % 10] = true;                efirst[2][i/1000] = true;                elast[2][i % 100] = true;                efirst[3][i/100] = true;                elast[3][i % 1000] = true;                efirst[4][i/10] = true;                elast[4][i % 10000] = true;            }            given_ins(&(givenlen[2][i/1000]), given[2][i/1000], (i/100)%10);            given_ins(&(givenlen[3][i/100]),  given[3][i/100],  (i/10)%10);        }    }    int base_cs[5] = {0,0,0,0,0};    search(0, base_cs, 0, 0);    if (none_so_far)        fout << "NONE" << endl;    return 0;}