Question Name:One-Sized Game

#include<bits/stdc++.h>
using namespace std;
//using namespace std::chrono;
#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define foo(i,x,n) for(int i=x;i<n;i++)
#define pp pair
vector<pp<ll,ll> > v;
int aa[100005];
void update(int inx)
{
    while(inx<100005)
    {
        aa[inx]+=1;
        inx+=inx&-inx;
    }
}
 
int getindex(int inx)
{   int ans=0;
   while(inx>0)
    {   ans+=aa[inx]; 
        inx-=inx&-inx;     
    }
    return ans;
}
void boost()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
}
 
int main() {
    boost();
    int t;cin>>t;while(t--)
    {	
    	ll x;int n;
    	cin>>n;
    	v.clear();
 
    
    for(int i=1;i<=n;i++)
        cin>>x,v.pb(mp(x,i));
      
 
    sort(v.begin(),v.end());
    
		
	int j=0;
	ll sub=0,previ=0;
	bool won=false;
	while(j<=n-1)
	{
   
	   if(v[j].f>=sub)
	   {
	   	if(j==n-1)
	   		won=true;
	    previ=v[j].s-getindex(v[j].s); 
	    
	    ll mul=(v[j].f-sub)/previ;
	    mul++;
	   sub=sub+mul*previ; 
	    
       }
       update(v[j].s);
	   j++; 
	}
	
	  if(!won)
	       cout<<"Kushagra\n";
	   else
	       cout<<"Ladia\n";
	
	memset(aa,0,sizeof(aa));
	}
	return 0;
}
  • Problem Description
    Ladia and Kushagra are playing the One-Sized Game. The rules of this game are pretty simple.

    They have an array consisting of N elements (1-indexed). In each step, one needs to find out the smallest element present in the array. Get the index of that element and subtract that value (index value) from every element of the array. If there is a clash/collision between the smallest element, pick the one that occurs first — that is the one having smaller index. This process is repeated several times. Whenever an element’s value goes below 0 this element gets removed from the array and the array gets re-sized.

    During the game’s play, if at any point of time, the array is left with only one element, Ladia wins the game otherwise Kushagra wins.

    Given an array consisting of N elements, print whether Ladia will win or Kushagra.

    Input:

    The first line contains an integer T denoting the number of test-cases. Each test case begins with an integer N that denotes the size of the array. This is followed up by N space separated integers.

    Output:

    For each test case print whether “Ladia” wins or “Kushagra” (without quotes).

    Constraints:

    1 <= T <= 
    1 <= N <= 10^5
    0 <= Array Value <= 10^9
  • Test Case 1
    Input (stdin)1
    4
    2 9 7 10

    Expected OutputLadia
  • Test Case 2
    Input (stdin)2
    3
    5 2 2
    3
    3 7 6

    Expected OutputLadia
    Kushagra

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.