/* 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/) Il programma implementa una strategia 1-look-ahead; non gioca ottimalmente, ma è molto semplice. */ #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 */ 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 play(short int *oldpit) //ricerca la mossa ottimale per il giocatore 1 con un look-ahead { short int pit[8]; int d, pmax; long int max = -100; for (int i = 0; i < 7; i++) if (oldpit[i] > 0) { move(i, oldpit, pit, d); if (d > max) { max = d; pmax = i; } } return pmax + 1; } void main() { for (int i = 0; i < 7; i++) { cin >> pit[i]; pit[7] += pit[i]; } 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)<