PALLGAME101 -Editorial

PROBLEM LINK:

Practice

Author: Kunal Demla
Editorialist: Kunal Demla

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a number of palindrome binary Strings and game rules, find optimal solution to win the game.

QUICK EXPLANATION:

Count the number of 0s in the string. Answer is constantly dependent on the same.

# EXPLANATION:
When No. of 0s = 0, Tie
When No. of 0s = 1, The one who moves 1st, looses.
When No. of 0s = 2, The one who moves 1st, looses as:

Lets take Players A and B, and String 1001: A uses move 1 to change it to 1101. B uses move 2 to change it to 1011. A uses move 1 to change it to 1111. B wins.

Using this we can derive that this is a subproblem to all other bigger numbers and it can be derived that:
When No. of 0s = odd, 1st player wins.
When No. of 0s = even, 2nd player wins.

ALTERNATE EXPLANATION:

The problem can be broken into parts and solved but it will just be a waste of time.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
    ll n,m,x,y,i,j,k;
    string s;
    cin>>s;
    n=0;
    for(auto ch:s){
        if(ch=='0')
        n++;
    }
    if(n==0)
        cout<<"Tie";
    else if(n==1)
        cout<<"Kunal";
    else if(n%2)
        cout<<"Anamika";
    else 
        cout<<"Kunal";
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t=1;
cin>>t;
int n=t;
while(t--)
{
    solve();
    cout<<"\n";
}

cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
return 0;
}