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.

- 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. - 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.
- 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.
- Without performing calculations, give the complexity of the previous function and justify your answer.

**Difficulty level**

**This exercise is mostly suitable for students**

```
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';
}
```

Back to the list of exercises

Looking for a more challenging exercise, try this one !!

Implement a stack using a heap