Poj Solution 2930

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

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;

#define count asdljflsdka
#define for_ii(k) for( ii[(k)]=0; ii[(k)]<m; ii[(k)]++ )

char a[20];
char w[110];

char e[6][4] = {
     { 1, 2, 3, 4 },
     { 0, 2, 4, 5 },
     { 0, 1, 3, 5 },
     { 0, 2, 4, 5 },
     { 0, 1, 3, 5 },
     { 1, 2, 3, 4 }
};

char num[20];
char answer[20];
int n, m;
int s[111][6];
bool flag[11][11][11][11][11][11];

void set( int a0, int a1, int a2, int a3, int a4, int a5 ) {
    flag[ a0 ][ a1 ][ a2 ][ a3 ][ a4 ][ a5 ] = true;
    flag[ a0 ][ a2 ][ a3 ][ a4 ][ a1 ][ a5 ] = true;
    flag[ a0 ][ a3 ][ a4 ][ a1 ][ a2 ][ a5 ] = true;
    flag[ a0 ][ a4 ][ a1 ][ a2 ][ a3 ][ a5 ] = true;
}

int clac() {
    int i, j, k, t, best = 0;
    for( i=0; i<6; i++ )
        s[0][i] = ( a[i] == w[0] );
        
    for( i=0; i<n-1; i++ )
    for( j=0; j<6; j++ )
    for( k=0; k<4; k++ )
    if( s[i+1][ e[j][k] ] < ( t = s[i][j] + ( a[ e[j][k] ] == w[i+1] ) ) )
        s[i+1][ e[j][k] ] = t;
    
    for( i=0; i<6; i++ )
        if( s[n-1][i] > best )
            best = s[n-1][i];
            
    return best;
}

int count[10];
int sign[10];

int main( ) {
    int i, ans, ii[6], h, c = 1;
    while( scanf( "%s", w ) == 1 ) {
        n = strlen( w );
        
        memset( count, 0, sizeof count );
        m = 0;
        
        for( i=0; i<n; i++ ) {
            w[i] -= '0';
            if( count[ w[i] ] == 0 )
                num[m++] = w[i];
            count[ w[i] ] ++;
        }
        
        ans = 0;
        if( count[ 0 ] == 0 )
            num[m++] = 0;
        sort( num, num+m );
        memset( flag, 0, sizeof flag );
                
        for_ii(0)for_ii(1)for_ii(2)for_ii(3)for_ii(4)for_ii(5) {
            
            memset( sign, 0, sizeof sign );
            h = 0;
            for( i=0; i<6; i++ ) {
                a[i] = num[ ii[i] ];
                if( !sign[ a[i] ] ) {
                    h += count[ a[i] ];
                    sign[ a[i] ] = true;
                }
            }
            if( h < ans ) continue;
            
            if( flag[ a[0] ][ a[1] ][ a[2] ][ a[3] ][ a[4] ][ a[5 ] ] )
                continue;
     
            set( a[0], a[1], a[2], a[3], a[4], a[5] );
            set( a[5], a[1], a[2], a[3], a[4], a[0] );
            set( a[1], a[0], a[2], a[5], a[4], a[3] );
            set( a[3], a[0], a[2], a[5], a[4], a[1] );
            set( a[2], a[1], a[0], a[3], a[5], a[4] );
            set( a[4], a[1], a[0], a[3], a[5], a[2] );

            set( a[0], a[4], a[3], a[2], a[1], a[5] );
            set( a[5], a[4], a[3], a[2], a[1], a[0] );
            set( a[1], a[4], a[5], a[2], a[0], a[3] );
            set( a[3], a[4], a[5], a[2], a[0], a[1] );
            set( a[2], a[5], a[3], a[0], a[1], a[4] );
            set( a[4], a[5], a[3], a[0], a[1], a[2] );
            
            memset( s, 0, sizeof s );
            
            h = clac();
            
            if( h >= ans ) {
                sort( a, a+6 );
                if( h > ans || ( h==ans && std::lexicographical_compare(a, a+6, answer, answer+6)  ) ) {
                    for( i=0; i<6; i++ )
                        answer[i] = a[i];
                }
                ans = h;
            }
        }
        
        printf( "Dice %d: discrepancy is %d, digits used:", c++, n-ans );
        for( i=0; i<6; i++ )
            printf( " %d", int(answer[i]) );
        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 *