Consider a game where two players (\(\textit{A}\) and \(\textit{B}\)) each have a bunch of \(\texttt{N}\) (constant) \$ banknotes (1, 5, 10, 20 , \(\cdots\)) arranged in any order, and a third person (\(\textit{C}\)) plays the role of the bank who has no banknotes at the start of the game.

Playing a shot consists in taking the first banknote of the player \(\textit{A}\) and comparing it to the first one of his opponent \(\textit{B}\). 

Let \(D\) = (value of the first \(\textit{A}\) banknote - value of the first \(\textit{B}\) banknote).

We distinguish the three following cases:

• \(D> 0\): B must give to \(\textit{A}\) the first $D$ banknotes of his bunch if the bunch contains enough banknotes, or all banknotes of his bunch otherwise. \textit{A} puts his first banknote and those given by \(\textit{B}\) up his bunch.
• \(D <0\): A must give to \(\textit{B}\) the first $D$ banknotes of his bunch. \(\textit{B}\) puts these banknotes up his bunch.
• \(D = 0\): both banknotes are lost and given to the bank \(\textit{C}\).

Example:

• Player \(\textit{A}\)
  \(\begin{array}{|c|c|c|c|c|c|c|}  \hline
  5 & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \hline
  \end{array}\)
• Player  \(\textit{B}\)
  \(\begin{array}{ |c|c|c|c|c|c|c|} \hline
  1 & 10 & 100 & 10 & 20 &\cdots & \cdots\\ \hline
  \end{array}\)
• \(\textit{B}\) must give to \(\textit{A}\) the first 4 banknotes (1, 10, 100, and 10).

A party is a succession of shots according to the above described model. The game ends when a player (\(\textit{A}\) or \(\textit{B}\)) has no more banknotes in his bunch; the other player wins the game.

1. What is the most adequate \(\texttt{ADT}\), seen in course, to model this problem? 
   In the following, you must use only the \(\texttt{ADT}\) operations mentioned in 1.
2. Write a function \(\texttt{shot(A,B,C)}\) that takes as input the 2 bunches \(\textit{A}\) and \(\textit{B}\) and an amount in the bank (\(\textit{C}\)) and updates them after a shot.
3. Write a function that simulates a party by taking as input two bunches \(\textit{A}\) and \(\textit{B}\) and that returns the winning player and the total amount of banknotes in the bank.
4. Without performing calculations, give the complexity of the previous function and justify your answer.

int shot(stack *p, char player, int i, int j, int *gain)
{
	stack q;
	int e,k,ei,ej;

	q=CreateStack();

	k=0;
	while(Top(*p,&e) && k<j)
	{
		Pop(p);
		Push(&q,e);
		k++;
		if(k==i) 
			ei=e;
	}
	if(k==j)
		ej=e;
	while(Top(q,&e))
	{
		Pop(&q);
		Push(p,e);
	}
	if(k>=j)
	{
		if(ei==ej)
			*gain+=2*ei;
		else
		{
			Push(p,ei);
			Push(p,ej);
		}
	}
	else if(k>=i) Push(p,ei);
	if(k<2) return 0;
	return 1;
}

void alea(int *i, int *j)
{
	*i=rand() % 3+1;
	*j=*i+rand() % 2+1;
}

char game(stack p)
{
	int gainA=0, gainB=0;
	int res;
	int i,j;

	do{
		alea(&i,&j);
		res=shot(&p,'A',i,j,&gainA);
		if(res && gainA<SUM)
		{
			alea(&i,&j);
			res=shot(&p,'B',i,j,&gainB);
		}
		printf("A=%d, B=%d\n",gainA,gainB);
	}while(res && gainA<SUM && gainB<SUM);

	if(gainA>=SUM) return 'A';
	else if(gainB>=SUM) return 'B';
}