GUESST04 - Editorial

editorial
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Vivek Kumar Mishra
Tester: Harshit Pandey
Editorialist: Harshit Sharma

DIFFICULTY:

EASY

PREREQUISITES:

Recursion

PROBLEM:

Find the Kth fruit on Nth level

QUICK EXPLANATION:

Use recursion to find the answer

EXPLANATION:

Let us assume the structure to be a tree where the root node will be Apple.
We have to find Kth fruit on the Nth level. Now, if the Kth Fruit of the Nth level is the left child of its parent fruit, then it will be of the same type, else it will be of the opposite type. This can be done recursively.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

string kthsol(int n, long long int k)
{
// Base Condition
if (n == 1 or k == 1)
{
return “A”;
}
long long int par = (k + 1) / 2;

string sol = kthsol(n - 1, par);

if (k == 2 * par - 1)
{
    return sol;
}
else
{
    if (sol == "A")
    {
        return "O";
    }
    else
    {
        return "A";
    }
}

}

void testcase()
{
int n, k;
cin >> n >> k;
cout << kthsol(n,k) << endl;
return;
}

int main()
{
int t;
cin >> t;
while(t–)
{
testcase();
}
}