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;
}