//Grzegorz Wierzowiecki 2005
//Rozwiązanei zadania Kamienie
#include <stdio.h>

//dla dodatkowych informacjii o działaniu programu
//#define DEB

#define MAX(a,b)  ( (a>b) ? (a) : (b) )
#define MIN(a,b)  ( (a<b) ? (a) : (b) )

typedef unsigned long int ULI;

int main(){
	ULI i,j,n,diff; //i numer kamiania z lewej , j numer kamienia z prawej
	ULI *k; //tablica kamieni
	ULI **t; //tablica przypadków
	//rozpatruje w niej tylo ile ja moge wygrać , bo i tak na końcu suma wygranych mojej i przecinika zawsze bedzie taka sama => wygrane się dopełniają
	ULI first;

	printf("Podaj liczbę kamieni:");
	scanf("%lu", &n);
	printf("Podaj teraz numery %lu kamieni oddzielone spacjami:\n", n);
	k = new ULI[n];
	for(i=0; i<n; ++i) scanf("%lu", &( k[i] ) );
	printf("Kto zaczyna? (0-algorytm 1-Ty): ");
	scanf("%lu", &first);

	//inicjujemy tylko trójkąt dla oszczedzenia pamięci
	// t[ numer lewego kamienia ][ number prawego kamienia ] = ile mozna wygrać
	t = new ULI*[n];
	for(i=0; i<n; ++i){
		t[i] = new ULI[ n-i ];
		t[i] -= i;
	}
	
	//Rozpatrzenie wszystkich przypadkow ze spamiętywaniem
	//Zaczynamy od tych dla kotórych j-i=0 i dochodzimy do poczatkowego j-i=(n-1)
	for(diff=0, i=0; i< n; ++i){
		j = i ; //prawy kamien dla czyelnosci
		if( diff == first ){ //Algola ruch
			t[i][j] = k[i]; //zyskuje ten kamien
		} else {  //przeciwnika
			t[i][j] = 0; //nie zyskuje nic bo przeciwnik zabiera kamien
		}
	}
	for(diff=1; diff<n; ++diff){ //diff od difference, czyli różnica
		for(i=0; i< (n-diff); ++i){
			j = i + diff; //dla czytelności prawa strona
			if( (diff%2) == first ){ //Teraz Algola ruch
				//tyle ile moge zyskać od teraz (w najgorszym razie)
				//to wartosc kamienia ktory zabieram + to co dalej moge zyskać
				t[i][j] = MAX( t[i+1][j] + k[i], t[i][j-1] + k[j] );
			} else { //teraz Przeciwnika
				//Przeciwnik wybiera dla mnie gorszy wariant
				t[i][j] = MIN( t[i+1][j], t[i][j-1] );
			}
#ifdef DEB
			printf( "(%lu, %lu) = %lu\n", i, j, t[i][j] );
#endif
		}
	}

	//Rozpoczynamy rozgrywkę
	ULI ile_algol=0, ile_przeciwnik=0, ruch, it;
	char wybor, str[100];
	for( i=0, j=n-1, ruch=0; ruch<n; ++ruch){
#ifdef DEB
		printf("     (%lu, %lu)      { L=%lu , P=%lu }\n", i,j, t[i+1][j]+k[i], t[i][j-1]+k[j] );
		printf("ALGORYTM: %lu  vs.\tPRZECIWNIK: %lu\n", ile_algol, ile_przeciwnik);
#endif
		printf("***************************************************\n");
		printf("Dostepne kamienie:\n");
		for(it=i; it<=j; ++it) printf(" %lu", k[it]);
		printf("\n");
		if( ( ruch %2 ) == first ){ //algol
			wybor = ( t[i+1][j]+k[i] > t[i][j-1]+k[j] ) ? 'L' : 'P' ;//lewa / prawa 
			ile_algol += k[ (wybor=='L') ? i : j ];
			printf("Algorytm: \tWybrałem %s kamien z numerem %lu.\n", (wybor=='L')?"lewy":"prawy", k[ (wybor=='L') ? i : j ] );
		} else {
			printf("Który kamien wybierasz ?  \t[L,P] :");
			//scanf("%c", &wybor);
			scanf("%s", str); wybor = str[0];
			ile_przeciwnik += k[ (wybor=='L') ? i : j ];
		}
		if( wybor == 'L' ) { ++i; } else { --j; };
		printf("\n");
	}
	printf("Wyniki:\nALGORYTM: %lu  vs.\tPRZECIWNIK: %lu\n", ile_algol, ile_przeciwnik);
		
	return 0;
}