Poj Solution 2842

http://poj.org/problem?id=2842

#include <stdio.h>


int an[10], bn[10];
int sa[10], sb[10];
int p[10], n, m, g, h;
int S[500000], T[500000];

int get_T( int *a ) {
    int index = 0, i;
    for( i=0; i<n; i++ )
        index += a[i]*sa[i];
    return T[ index ];
}

int get_S( int *a ) {
    int index = 0, i;
    for( i=0; i<n; i++ )
        index += (a[i]+p[i])*sb[i];
    return S[ index ];
}

bool check( ) {
    int a[10] = { 0 }, i, k;
    for( i=0; i<m; i++ ) {
        if( get_T( a ) != get_S( a ) )
            return false;
        for( k=n-1; a[k] == an[k]-1 && k; k-- )
            ;
        a[k]++;
        while( k++ < n-1 )
            a[k] = 0;
    }
    return true;
}

void search( ) {
    int i, k;
    for( i=0; i<g; i++ ) {
        if( check( ) )
            return;
        for( k=n-1; p[k] == bn[k]-an[k] && k; k-- )
            ;
        p[k]++;
        while( k++ < n-1 )
            p[k] = 0;
    }
    return;
}

int main( ) {
    int i;
    g = m = h = 1;

    scanf( "%d", &n );

    for( i=0; i<n; i++ )
        scanf( "%d", bn+i );
    for( i=0; i<n; i++ ) {
        scanf( "%d", an+i );
        m *= an[i];
        g *= bn[i]-an[i]+1;
        h *= bn[i];
    }

    for( i=0; i<h; i++ )
        scanf( "%d", S+i );
    for( i=0; i<m; i++ )
        scanf( "%d", T+i );

    sb[n-1] = sa[n-1] = 1;

    for( i=n-2; i>=0; i-- ) {
        sa[i]=an[i+1]*sa[i+1];
        sb[i]=bn[i+1]*sb[i+1];
    }

    search( );
    for( i=0; i<n; i++ )
        printf( "%d ", p[i]+1 );
    printf( "n" );
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *