/* Ioiwari (IOI 2001) Copyright (C) 2002 Paolo Boldi This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA (Come per tutti i problemi del 2001, è utile leggere il libretto distribuito dagli organizzatori, e disponibile nella sezione "Materiale didattico" della home page http://ioi.dsi.unimi.it/. Inoltre, per fare gareggiare due programmi potete utilizzare il referee che trovate su http://ioi.dsi.unimi.it/problemi/) Per capire come funziona questo programma, è necessario prima leggere la dispensa sulla teoria dei giochi che trovate su http://ioi.dsi.unimi.it/. Il programma implementa una strategia MiniMax. Compilandolo senza opzioni, gioca come previsto dal testo. - Con l'opzione -DAVVERSARIO, gioca per secondo - Con l'opzione -DRISULTATO, alla fine stampa quanto ha guadagnato/perso */ #include #include /* Uno stato di gioco è definito da un numero di 7 cifre in base 6: a partire dalla cifra meno significativa sono indicati i contenuti delle 7 buche */ #define STATI 6*6*6*6*6*6*6 typedef int stato; /* Se entrambi giocano in modo ottimale, e si parte dallo stato s, p[s] contiene il numero di palline nette guadagnate da chi muove per primo (nette significa "numero palline guadagnate da lui - numero di palline guadagnate dall'avversario". La matrice viene riempita dalla procedura minimax. Inoltre m[s] contiene la buca da svuotare nella strategia ottima quando ci si trova nello stato s. */ int p[STATI-1]; int m[STATI-1]; /* Guarda se nello stato s la buca b è vuota. Se sì, restituisce 0 per indicare che una mossa non è possibile. In caso contrario, restituisce 1 e mette: - in *t il nuovo stato raggiunto - in *g il numero di palline guadagnate da chi ha fatto la mossa meno quelle guadagnate dall'avversario */ int prossimostato( stato s, int b, stato *t, int *g ) { int ss[7], i, mano; for ( i = 0; i < 7; i++ ) { ss[i] = s % 6; s /= 6; } if ( ss[b] == 0 ) return 0; /* Mossa impossibile */ *g = 0; mano = ss[b]; ss[b] = 0; while ( mano > 0 ) { b = ( b + 1 ) % 7; if ( mano > 1 ) if ( ss[b] == 5 ) { ss[b]--; (*g)++; } else { mano--; ss[b]++; } else if ( ss[b] > 0 && ss[b] < 5 ) { (*g) += mano + ss[b]; ss[b] = mano = 0; } else { (*g) -= mano; mano = 0; } } *t = 0; for ( i = 6; i >= 0; i-- ) { *t = 6*(*t) + ss[i]; } return 1; } /* Calcola e restituisce p[s]; dopo averla chiamata, per ogni configurazione s' raggiungibile da s, p[s'] conterrà il valore corretto. Se muovi=1, stampa la mossa ottima da fare. */ int minimax( stato s ) { int indottimo, ottimo, i, g, gg; stato t; if ( m[s] >= 0 ) return p[s]; /* Configurazione già visitata */ if ( s == 0 ) return ( p[s] = 0 ); ottimo = -INT_MAX; for ( i = 0; i < 7; i++ ) { if ( prossimostato( s, i, &t, &g ) ) { gg = minimax( t ); /* Quanto guadagnerebbe l'avversario a partire da t */ if ( g-gg > ottimo ) { ottimo = g-gg; indottimo = i; } } } m[s] = indottimo; return ( p[s] = ottimo ); } /* Inizializza la matrice m[] a -1. */ void init() { int i; for ( i = 0; i < STATI; i++ ) m[i] = -1; } int main() { int i, v, g, ss[7], gtot = 0, firstmove = 1; stato s = 0, t; init(); for ( i = 0; i < 7; i++ ) scanf( "%d", &ss[i] ); for ( i = 6; i >= 0; i-- ) s = 6*s + ss[i]; minimax( s ); #ifdef AVVERSARIO if ( !s ) return 0; scanf( "%d", &i ); prossimostato( s, i-1, &t, &g ); gtot -= g; s = t; #endif while ( s ) { printf( "%d\n", m[s]+1 ); fflush( stdout ); prossimostato( s, m[s], &t, &g ); gtot += g; s = t; if ( !s ) break; scanf( "%d", &i ); prossimostato( s, i-1, &t, &g ); gtot -= g; s = t; } #ifdef RISULTATO fprintf( stderr, "GUADAGNO TOTALE: %d\n", gtot ); fprintf( stderr, "%s\n", gtot>0? "Ho vinto!": gtot<0? "Ho perso":"Pareggio" ); #endif return 0; }