0w1

IOI'94 The Primes ( 暴搜 + 枚舉順序剪枝 )

PEG Judge - IOI '94 - The Primes
不停的 TLE,原來枚舉的順序影響這麼大呢。。
首先最好枚舉兩個對角線,因為他們影響的最大。
f:id:h0rnet:20160302004832p:plain
接著枚舉外面兩行,所以我們要事先紀錄中間那三個數字總和為多少且頭尾為多少的質數有哪些。
f:id:h0rnet:20160302004829p:plain
再來我們發現這兩個格子可以 O( 1 )直接利用 sum算出來。
f:id:h0rnet:20160302004827p:plain
所以旁邊這兩行分別枚舉出來後,中間這兩個格子也可以用 O( 1 )算出來。
f:id:h0rnet:20160302004824p:plain
注意只要一發現矛盾就要立刻淘汰,否則一定會超時。一開始為了方便編寫我都留到最後才判斷,結果真的 TLE海。只要有新的一排數字確定,就要立刻判斷它是否為質數,和是否相同。另外枚舉周圍四個數的時候,因為題目規定開頭不能有領導 0,所以一開始預處理的時候就可以依據開頭數,結尾數和中間三個數字的總和,並確定都不包含 0再押進該類的 vector。
一直漏判一些東西,幸好有確實用 assert()讓我很快就找到 bug。最後竟然是忘了判空解的情況讓我除錯最久。

#include <bits/stdc++.h>
using namespace std;

int getSum(int x){
    int res = 0;
    while( x > 0 ) res += x % 10, x /= 10;
    return res;
}

int getSum3(int x){
    return getSum( x / 10 % 1000 );
}

int sum, fd; // sum, first digit
vector<int> ph[ 10 ], pm[ 10 ], pt[ 10 ]; // prime numbers of head, mid and tail
vector<int> pht3n0[ 10 ][ 10 ][ 9 * 3 + 1 ]; // prime numbers of head, tail and sum3, no 0 allowed

bool isPrime(int x){
    if( x < 10000 ) return false; // no leading zero
    assert( x > 10 );
    if( !( x & 1 ) ) return false;
    int sx = sqrt( x ) + 1;
    for(int i = 3; i <= sx; i += 2)
        if( x % i == 0 )
            return false;
    return true;
}

bool no0(int x){
    for(int i = 0; i < 5; ++i){
        if( x % 10 == 0 ) return false;
        x /= 10;
    }
    return true;
}

void prePrime(){
    for(int i = 10000; i <= 99999; ++i)
        if( i & 1 )
            if( isPrime( i ) )
                if( getSum( i ) == sum ){
                    int h = i / 10000;
                    int m = i / 100 % 10;
                    int t = i % 10;
                    ph[ h ].push_back( i );
                    pm[ m ].push_back( i );
                    pt[ t ].push_back( i );
                    if( no0( i ) )
                        pht3n0[ h ][ t ][ getSum3( i ) ].push_back( i );
                }
}

int mat[ 7 ][ 7 ]; // 1 - indexed

int getNum(int r1, int r2, int c1, int c2){
    int res = 0;
    for(int i = r1; i <= r2; ++i)
        for(int j = c1; j <= c2; ++j)
            res = res * 10 + mat[ i ][ j ];
    return res;
}

int getSum(int r1, int r2, int c1, int c2){
    int res = 0;
    for(int i = r1; i <= r2; ++i)
        for(int j = c1; j <= c2; ++j)
            res += mat[ i ][ j ];
    return res;
}

void write(int op, int n, int x){ // op: 0: r, 1: c, n: which row / column
    if( op == 0 ){
        for(int j = 5; j >= 1; --j)
            mat[ n ][ j ] = x % 10, x /= 10;
    } else if( op == 1 ){
        for(int i = 5; i >= 1; --i)
            mat[ i ][ n ] = x % 10, x /= 10;
    } else if( op == 2 ){ // diagonal
        if( n == 1 ){
            mat[ 2 ][ 2 ] = x / 1000 % 10;
            mat[ 3 ][ 3 ] = x / 100 % 10;
            mat[ 4 ][ 4 ] = x / 10 % 10;
        } else{
            mat[ 2 ][ 4 ] = x / 10 % 10;
            assert( mat[ 3 ][ 3 ] == x / 100 % 10 );
            mat[ 3 ][ 3 ] = x / 100 % 10;
            mat[ 4 ][ 2 ] = x / 1000 % 10;
        }
    }
}

bool isDig(int x){
    return 0 <= x && x <= 9;
}

set<string> ans;

void updateAns(){
    string s;
    for(int i = 1; i <= 5; ++i)
        for(int j = 1; j <= 5; ++j){
            assert( 0 <= mat[ i ][ j ] && mat[ i ][ j ] <= 9 );
            s += (char)( mat[ i ][ j ] + '0' );
        }
    ans.insert( s );
}

void judge(int r1, int c1, int r5, int c5){
    if( getSum( 3, 3, 1, 5 ) != sum || getSum( 1, 5, 3, 3 ) != sum ) return; 
    if( !isPrime( getNum( 3, 3, 1, 5 ) ) || !isPrime( getNum( 1, 5, 3, 3 ) ) ) return;
    updateAns();
}

void printAns(){
    if( ans.empty() ){ // FORGOT THIS = =
        puts("NONE");
        return;
    }
    bool first = true;
    assert( ans.size() );
    for(auto a: ans){
        assert( a.size() == 25 );
        if( first ) first = false;
        else puts("");
        for(int i = 0; i < a.size(); ++i){
            printf("%c", a[ i ]);
            if( ( i + 1 ) % 5 == 0 ) puts("");
        }
    }
}

void solve(){
    prePrime();
    for(auto d1: ph[ fd ]){ // diagonal lu to rd
        write( 2, 1, d1 );
        int d1m = d1 / 100 % 10;
        for(auto d2: pm[ d1m ]){ // diagonal ld to ru
            write( 2, 2, d2 );
            int r1h = d1 / 10000, r1t = d2 % 10;
            int r1s = sum - r1h - r1t;
            int c1h = d1 / 10000, c1t = d2 / 10000;
            int c1s = sum - c1h - c1t;
            int r5h = d2 / 10000, r5t = d1 % 10;
            int r5s = sum - r5h - r5t;
            int c5h = d2 % 10, c5t = d1 % 10;
            int c5s = sum - c5h - c5t;
            if( r1s < 0 || c1s < 0 || r5s < 0 || c5s < 0 ) continue;
            if( r1s > 27 || c1s > 27 || r5s > 27 || c5s > 27 ) continue;
            for(auto r1: pht3n0[ r1h ][ r1t ][ r1s ]){
                write( 0, 1, r1 );
                for(auto r5: pht3n0[ r5h ][ r5t ][ r5s ]){
                    write( 0, 5, r5 );
                    mat[ 3 ][ 2 ] = sum - ( getSum( 1, 5, 2, 2 ) - mat[ 3 ][ 2 ] );
                    mat[ 3 ][ 4 ] = sum - ( getSum( 1, 5, 4, 4 ) - mat[ 3 ][ 4 ] );
                    if( !isDig( mat[ 3 ][ 2 ] ) || !isDig( mat[ 3 ][ 4 ] ) ) continue;
                    if( !isPrime( getNum( 1, 5, 2, 2 ) ) || !isPrime( getNum( 1, 5, 4, 4 ) ) ) continue;
                    for(auto c1: pht3n0[ c1h ][ c1t ][ c1s ]){
                        write( 1, 1, c1 );
                        for(auto c5: pht3n0[ c5h ][ c5t ][ c5s ]){
                            write( 1, 5, c5 );
                            mat[ 2 ][ 3 ] = sum - ( getSum( 2, 2, 1, 5 ) - mat[ 2 ][ 3 ] );
                            mat[ 4 ][ 3 ] = sum - ( getSum( 4, 4, 1, 5 ) - mat[ 4 ][ 3 ] );
                            if( !isDig( mat[ 2 ][ 3 ] ) || !isDig( mat[ 4 ][ 3 ] ) ) continue;
                            if( !isPrime( getNum( 2, 2, 1, 5 ) ) || !isPrime( getNum( 4, 4, 1, 5 ) ) ) continue;
                            judge( r1, c1, r5, c5 );
                        }
                    }
                }
            }
        }
    }
    printAns();
}

int main(){
    scanf("%d%d", &sum, &fd);
    solve();
    return 0;
}