/* Ioiwari (IOI 2001) Copyright (C) 2002 Luca Foschini 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. */ #include short int pit[8]; /* contiene il numero di palline in ogni buca i i=0..6 pit[7] contiene il numero totale di palline */ const long int Nmax = 6 * 6 * 6 * 6 * 6 * 6 * 6; const int INT32_MAX = 2147483647; const int INT32_MIN = -2147483647 - 1; int board[2][Nmax]; /* descrive lo spazio di gioco Dato che in ogni buca possono stare al max 5 palline e vi sono 7 buche, ogni configurazione e' rappresentabile con 7 numeri in base 6 Inoltre rappresenta il DAG su cui verra' fatta la computazione max-min */ void reset() //mette a -1 tutte le celle di board { for (int j = 0; j < 2; j++) for (long int i = 0; i < Nmax; i++) board[j][i] = INT32_MAX; } inline long int value(short int *pit) /* A partire dalla lista di valori contenuti in pit (numeri da 0 a 5) calcola e restituisce il numero in base 10 corrispondente */ { long int val = pit[0]; for (short int i = 1; i < 7; i++) val = val * 6 + pit[i]; return val; } inline void move(short int m, short int *oldpit, short int *pit, int &d) /* Esegue una mossa (m) e restituisce in pit la nuova situazione di gioco e in d la differenza tra il numero di palline contenute nelle banche dei due giocatori , derivata dalla mossa m */ { for (short int i = 0; i <= 7; i++) pit[i] = oldpit[i]; short int hand = pit[m]; pit[7] -= pit[m]; pit[m] = 0; d = 0; while (hand) { (++m) %= 7; if (hand > 1) { if (pit[m] == 5) { pit[m]--; pit[7]--; d++; } else { hand--; pit[m]++; pit[7]++; } } else { if (pit[m] % 5 == 0) { d--; hand--; } else { d += (pit[m] + 1); pit[7] -= pit[m]; pit[m] = 0; hand--; } } } } int diff(short int *oldpit, short int turn) { /* recursive */ /* riempie ricorsivamente la tabella board board[t][B] contiene con la massima differenza di punti tra i due giocatori a favore del giocatore t, a partire dalla configurazione di gioco B nell'ipotesi che il giocatore 2 giochi in modo ottimale */ short int pit[8]; int d; if (board[turn][value(oldpit)] == INT32_MAX) { if (turn == 0) { long int max = INT32_MIN, val; for (int i = 0; i < 7; i++) if (oldpit[i] > 0) { move(i, oldpit, pit, d); val = d + diff(pit, 1); if (val > max) max = val; } board[0][value(oldpit)] = max; return max; } else { int min = INT32_MAX, val; for (int i = 0; i < 7; i++) if (oldpit[i] > 0) { move(i, oldpit, pit, d); val = diff(pit, 0) - d; if (val < min) min = val; } board[1][value(oldpit)] = min; return min; } } else return board[turn][value(oldpit)]; } int play(short int *oldpit) //ricerca la mossa ottimale per il giocatore 1 consultando board { short int pit[8]; int d, pmax; int max = INT32_MIN; for (int i = 0; i < 7; i++) if (oldpit[i] > 0) { move(i, oldpit, pit, d); if (d + board[1][value(pit)] > max) { max = d + board[1][value(pit)]; pmax = i; } } return pmax + 1; } void main() { for (int i = 0; i < 7; i++) { cin >> pit[i]; pit[7] += pit[i]; } reset(); board[0][0] = 0; board[1][0] = 0; diff(pit, 0); int mymove, last, d; //,dfbank=0; while (pit[7]) { mymove = play(pit); cout << mymove << endl << flush; move(mymove - 1, pit, pit, d); // dfbank+=d; if (pit[7] == 0) continue; cin >> last; last--; move(last, pit, pit, d); // dfbank-=d; } // cerr <<"esito:" << ((dfbank>0)?0:1)<