ADAGAME - Ada and Game - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : ADAGAME

👉 Hint : 3D DP with 3rd dimension representing player with turn

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
int dp[10000][101][2];
int v;
int AdaGame(int n,int m,int t)
{
    int i;
    if(m==0)
    {
        if(n>v)
            return 1;
        return 0;
    }
    if(dp[n][m][t]!=-1)
        return dp[n][m][t];
    if(t==0)
        dp[n][m][t]=0;
    else
        dp[n][m][t]=1;
    string s="0000";
    s+=to_string(n);
    for(int k=0;k<4;k++)
    {
        i=s.length()-1-k;
        if(s[i]-'0'<9)
        {
            s[i]+=1;
        
            if(t==0)
            {
                dp[n][m][t]=max(dp[n][m][t],AdaGame(stoi(s),m-1,1));
            }
            else
            {
                dp[n][m][t]=min(dp[n][m][t],AdaGame(stoi(s),m-1,0));
            }
            s[i]-=1;        
        }
        else
        {
            s[i]-=9;
            
            if(t==0)
            {
                dp[n][m][t]=max(dp[n][m][t],AdaGame(stoi(s),m-1,1));
            }
            else
                {
                dp[n][m][t]=min(dp[n][m][t],AdaGame(stoi(s),m-1,0));
            }
            s[i]+=9;    
        }
    }
    return dp[n][m][t];
 
}
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        string s;
        cin>>n>>m;
        v=n;
        memset(dp,-1,sizeof(dp));
        bool b=AdaGame(n,m,0);
        if(b)
            cout<<"Ada"<<endl;
        else
            cout<<"Vinit"<<endl;
    }
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.