Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular price value.
The price of $i$th apple is $p_i$.
In this game, the players Foo and bar make an alternative move.
In each move, the player does the following:
- If there is more than one apple left, the player tosses an unbiased coin. If the outcome is head, the player takes the first apple among the apples that are currently present in a row in a straight line.
- If there is a single apple left, te player takes it.
The goal here is to calculate the expected total price value that Foo will get if Foo plays first.
Example 1:
N=5
Apple price val:
5 2 3 1 5
Answer is : 11.00
Example 2:
N=6
7 8 2 3 7 8
Answer : 21.250
Example 3:
N=3
1 4 9
First Second Third Foo Total Val
Foo gets 1 Bar gets 4 Foo gets 9 10
Foo gets 1 Bar gets 9 Foo gets 4 5
Foo gets 9 Bar gets 1 Foo gets 4 13
Foo gets 9 Bar gets 4 Foo gets 1 10
probability 0.5 • 0.5 = 0.25.
Expected value (Foo)= (0.25 *10 )+ (0.25 *5) + (0.25*13)+ (0.25*10) = 9.500
I wrote the following code:
#include<iostream>
using namespace std;
double calculate(int start,int end,int num,int current);
int arr[2010];
int main()
{
int T;
scanf("%d",&T);
for(int t=0;t<T;t++)
{
int N;
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%d",&arr[i]);
}
printf("%.3lf\n",calculate(0,N-1,N/2+N%2,0));
}
return 0;
}
double calculate(int start,int end,int num,int current)
{
if(num==current)
return 0;
double value=0;
value=.5*arr[start]+.5*arr[end]+.5*calculate(start+1,end,num,current+1)+.5*calculate(start,end-1,num,current+1);
return value;
}
But the above code is quite slow. The constraints are: price of apples $p_i \le 1000$; $1 \le N \le 2000$; there are 500 test cases. How can I solve this more efficiently?
