MCOINS - Coins Game - Solution

MCOINS - Coins Game is an easy bottom-up DP problem.

I am assuming that you have already understood the problem statement, otherwise go back and read the problem statement again.

In this problem, we have made an array b[] which contains height of different towers, and we have to print a string containing A and B, who's ith element represent the player who will win for the ith tower. Now we have to print A if first player wins and B if second player wins.

Now, we have an array a[], which contains result of all towers.

Each player can choose 1,K or L to remove from tower, so if there is a tower with height 1, first player will win. So, we keep a[1] = 1

Now, for every i, A can win only if
a[i-1] = 0 or a[i-K] = 0 or a[i-L] = 0

otherwise B will win.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

	#include "bits/stdc++.h"
	using namespace std;
	typedef unsigned long long ull;
	typedef long long int ll;
	typedef vector<long long int> vi;
	typedef pair<int, int> ii;
	typedef vector<ii> vii;
	int a[1000009];
	int main()
	{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	ll n,sum=0,count=0,m,flag=0,ans=0,maxi=0,k,l;
	cin>>k>>l>>m;
	int b[51];
	for(int i=0;i<m;i++)
	{
	ll x;
	cin>>x;
	if(x>maxi)
	maxi=x;
	b[i]=x;
	}
	a[1]=1;
	for(int i=2;i<=maxi;i++)
	{
	if(!a[i-1])
	a[i]=1;
	if(i-k>=0&&!a[i-k])
	a[i]=1;
	if(i-l>=0&&!a[i-l])
	a[i]=1;
	}
	for(int i=0;i<m;i++)
	{
	if(a[b[i]])
	cout<<"A";
	else cout<<"B";
	}
	return 0;
	}
	/* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	*/

view raw MCOINS.cpp hosted with ❤ by GitHub