Given N pots of gold placed in a line. The number of coins contained in pot i is represented by A[i]. Two player start playing the game. In each turn a player will pick the pot either from the beginning or from the end of the line. The selected pot will be removed from the line. Assuming both player play optimally write algorithm to decide who will win. A and B are players, assume A starts first.
Solution O(n^2) sol.
Compute
P[i][j] = max {A[i] - P[i+1][j], A[j] - P[i][j-1]} + S[i][j] for all i<j
P[i][i] = A[i]
P[0][N-1] will be coin gathered by A (player playing first)
S[0][N-1] - P[0][N-1] would be coins gathered by B (player playing second).
Test case
N=4 (5,20, 4,1) --> A wins
N=5 (5,5, 20, 1, 1) --> B wins
N=5 (5 5 20 8 14) --> A wins
N=5 (5 5 20 1 14) --> B win
Working Code
Solution O(n^2) sol.
Compute
P[i][j] = max {A[i] - P[i+1][j], A[j] - P[i][j-1]} + S[i][j] for all i<j
P[i][i] = A[i]
P[0][N-1] will be coin gathered by A (player playing first)
S[0][N-1] - P[0][N-1] would be coins gathered by B (player playing second).
Test case
N=4 (5,20, 4,1) --> A wins
N=5 (5,5, 20, 1, 1) --> B wins
N=5 (5 5 20 8 14) --> A wins
N=5 (5 5 20 1 14) --> B win
Working Code
#include <stdio.h>
#include <iostream>
#define max(a,b) a>b?a:b
using namespace std;
int main() {
int n,s;
cin>>n;
int a[n];
int sum[n][n];
for(int i=0;i<n;i++) {
cin>>a[i];
for(int j=0;j<i;j++) {
sum[i][j] = sum[i][j-1] + a[i];
}
sum[i][i] = a[i];
}
s = sum[0][n-1];
for(int i=n-2;i>=0;i--) {
for(int j=i+1;j<n;j++) {
sum[i][j] += max(a[i]-sum[i+1][j],a[j]-sum[i][j-1]);
}
}
if(sum[0][n-1] > s - sum[0][n-1])cout<<"A wins"<<endl;
else cout<<"B wins"<<endl;
return 0;
}
No comments:
Post a Comment