Foo and <PERSON> Game of Strategy
Foo and <PERSON> is 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. 17
Each apple has a particular price value.
The price of ith apple is pi for i=1 to N.
In this game,
the players <PERSON> and <PERSON> make an alternative move.
In each move, the player does the following: -If there is only one apple left, the player toss the coin and if its head, the player takes the first apple among the apples that are currently present in a row in a straight line , otherwise, the last apple is taken by the player.
The goal here is to calculate the expected total price value, <PERSON> will get if <PERSON> Plays First.
Note:
The coin is Unbiased. Probability of head is 0.50 and similar is the probability of tail. Total Price Value=summation of price value of all the apples, <PERSON> will get.
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 <PERSON> gets 1 <PERSON> gets 4 <PERSON> gets 9 10 <PERSON> gets 1 <PERSON> gets 9 <PERSON> gets 4 5 <PERSON> gets 9 <PERSON> gets 1 <PERSON> gets 4 13 <PERSON> gets 9 Bar gets 4 <PERSON> gets 1 10
probability 0.5 • 0.5 = 0.25. Expected value (Foo)= (0.25 10 )+ (0.25 5) + (0.2513)+ (0.2510) = 9.500
I wrote the following code:
#include 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=.5arr[start]+.5arr[end]+.5calculate(start+1,end,num,current+1)+.5calculate(start,end-1,num,current+1); return value; }
But the above code is quite slow ,as the constraints are price of apple<=1000 and 1<=N<=2000 and there are 500 test cases.
How to solve it in must efficient way ? 268