//Grzegorz Wierzowiecki 2005
//Rozwiazanie do Kamieni opierające się na dynamicznej sieci przypadków.
//Dzięki temu czas oczekiwania przed pierwszym ruchem może być mniejszy niż O(n^2)
//
//Może to być istotne, gdy jest limit czasowy na jeden ruch.
//
//Za to podejrzewam że całkowity czas działania programu jest w średnim przypadku dłuższy niż przy rozwiązaniu co generuje najpierw w n^2 drzewo wszystich przypadków.
//
//Niemnie jednak przy limicie czasowym na jeden ruch może ten algorytm okazać się lepszym rozwiazaniem.
//
//Albo kiedy nie można buforować wyników obliczeń. Np. w obiąrzonym bardzo serwisie www. Gdzie gra jednocześnie 100'000 osób
#include <stdio.h>

//umowna nieskonczonosc
#define INF ( 2000000 )

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

#ifdef DEB
#define PRINTVAL( v ) printf("%s = %lu\n", "" #v "" , v );
#endif

typedef unsigned long int ULI;

ULI n; //ilosc elementow
ULI *k; //tablica kamieni
ULI node_counter=0;

//rozpatruje w wezlach tylko ile ja moge wygrać , bo i tak na końcu suma wygranych mojej i przecinika zawsze bedzie taka sama => wygrane się dopełniają

class minnode;
class maxnode;

class maxnode{ //moj rouch. Wybieram maxymalna wartosc
	public:
		maxnode():nl(NULL),nr(NULL),l(NULL),r(NULL) {};
		ULI w, kl, kr; // w -wartosc | kl,kr - numer lewego/prawego kamienia
 		maxnode *nl, *nr; // neighbour - sąsiedzi, lewy i prawy
		minnode *l, *r; // synowie - lewy i prawy
			
		void init( ULI i, ULI j ); // i,j numery lewego i prawego kamienia
		ULI getVal();
		bool can_be_smaller( ULI val ); //czy może mieć mniejsza wartość od val ?
		void makenr(); //gdyby nl było null to doalokowuje
		void makel(); void maker(); //upewnij sie ze mam synow, jak nie to stórz
		inline maxnode * getnr() { 	makenr(); 	return nr; };
		inline minnode * getl() {	makel();	return l; };
		inline minnode * getr() {	maker(); 	return r; };
};

class minnode{ //ruch przeciwnika. Wybiera najgorsza dla mnie opcje
	public:
		minnode():nl(NULL),nr(NULL),l(NULL),r(NULL) {};
		ULI w, kl, kr; // w -wartosc | kl,kr - numer lewego/prawego kamienia
 		minnode *nl, *nr; // neighbour - sąsiedzi, lewy i prawy
		maxnode *l, *r; // synowie - lewy i prawy
		
		
		void init( ULI i, ULI j ); // i,j numery lewego i prawego kamienia
		ULI getVal();
		bool can_be_bigger( ULI val); //czy moze miec wieksza wartosc od val ?
		void makenr();
		void makel(); void maker(); //upewnij sie ze mam synow, jak nie to stórz
		inline minnode * getnr(){ 	makenr();	return nr; };
		inline maxnode * getl() {	makel();	return l; };
		inline maxnode * getr() { 	maker();	return r; };
};

class gra_kamienie{
	public:
		maxnode *proot; //w razie chęci implementacjii oczyszczania pamięci
		maxnode *pmove; //aktualny ruch , aby przeskok na nowa pozycje był w O( 1 )
		gra_kamienie():proot(NULL),pmove(NULL) {};
		
		void move( ULI kl, ULI kr ){
			if( pmove == NULL ){
				proot = pmove = new maxnode();
				pmove->init( kl, kr );
				return ;
			};
			if( pmove->kl == kl && pmove->kr == kr ) return ;
			//Wędrujemy w duł drzewa po lewych głęziach
			//Roznica miecy lewym i prawym kamieniem , dobrze określa poziom
			while( (pmove->kr - pmove->kl) > (kr - kl) )
				pmove = ( pmove->getl() )->getl();
			//A teraz w prawo jak potrzeba
			while( pmove->kl < kl ) 
				pmove = pmove->getnr();
#ifdef DEB
			//Jezeli blad w implemetnacjii lub zalożeniach to wygeneruje sie tu komunikat o bledzie
			if( pmove->kl != kl || pmove->kr != kr ) printf("Blad w funkcjii gra_kamienie::move(ULI,ULI) : \n");
#endif
		}

		char whattodo( ULI kl, ULI kr ){
			move( kl, kr );
			//jezeli wartosc obecnego ruchu jest taka jakbysmy poszli w lewo
			// to pojdźmy w lewo (lewa gałąź to zabranie prawego kamienia)
			if( kl == kr ){ //czy to ostatni ruch ?
				return 'L';
			}; 
			return ( pmove->getVal() == ( k[ kr ] + (pmove->getl())->getVal() ) ) ? 'P' : 'L';
		}
};

int main(){
	ULI i,j; 
	ULI first;
	gra_kamienie *gra = new gra_kamienie();

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

	//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("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 = gra->whattodo(i,j);
			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);
	printf("Zaalokowanych węzłów sieci kamieni alfa-beta-obcinanych ;-) : %lu\n", node_counter );

	return 0;
}

//Inicjacja MIN i MAX
void maxnode::init( ULI i, ULI j ) {
	kl = i; kr = j;
	this->w = ( kl == kr ) ? k[kl] : INF; 
	++node_counter ;
#ifdef DEB
	printf("minnode::init( %lu, %lu )\n", i, j );
#endif
}

void minnode::init( ULI i, ULI j ) {
	kl = i; kr = j;
	this->w = ( kl == kr ) ? k[kl] : INF; 
	++ node_counter ;
#ifdef DEB
	printf("minnode::init( %lu, %lu )\n", i, j );
#endif
}

// Wartosci podawanie i szacowanie ograniczenia - dla MIN i MAX
ULI maxnode::getVal(){
	if( w != INF ) return w;
	makel();
	w = l->getVal() + k[ kr ] ;
	maker();
	if( ! r->can_be_bigger( w - k[ kl ] ) )
		return w;
	if( w < ( r->getVal() + k[ kl ] ) ) 
		w = r->getVal() + k[ kl ] ;
	return w;
}

bool maxnode::can_be_smaller( ULI val ){
	if( w != INF ) return (w < val);
	makel();
	if( ( k[ kr ] + l->getVal() ) >= val ) return false;
	return true;
}

ULI minnode::getVal(){
	if( w != INF ) return w;
	makel();
	w = l->getVal() + 0 ; // + 0 zeby zaznaczyc ze nic nie zyskuje
	maker();
	if( ! r->can_be_smaller( w ) )
		return w;
	if( w > r->getVal() ) 
		w = r->getVal() ;
	return w;
}

bool minnode::can_be_bigger( ULI val ){
	if( w != INF ) return (w > val);
	makel();
	if( l->getVal() <= val ) return false;
	return true;
}

// Zaradzanie pamiecia. Alokowanie sąsiadów i synów
void maxnode::makel(){
	if( l != NULL ) return ;
	if( kl == 0 ){
		l = new minnode();
		l->init( 0, kr-1 );
		return ;
	}; // => że nl != null
	l = nl->getr(); // moj lewy to prawy syn sasiada lewego
}

void maxnode::maker(){
	if( r != NULL ) return ;
	makel();
	r = l->getnr();
}

void maxnode::makenr(){
	if( nr != NULL ) return ;
	nr = new maxnode();
	nr->init( kl+1, kr+1 );
	nr->nl = this;
}

void minnode::makel(){
	if( l != NULL ) return ;
	if( kl == 0 ){
		l = new maxnode();
		l->init( 0, kr-1 );
		return;
	}; // => żę nl != null
	l = nl->getr();
}

void minnode::maker(){
	if( r != NULL ) return ;
	makel();
	r = l->getnr();
}

void minnode::makenr(){
	if( nr != NULL ) return ;
	nr = new minnode();
	nr->init( kl+1, kr+1 );
	nr->nl = this;
}