HEALER - Editorial

PROBLEM LINK:

Practice

Author: Ayesha Uzma
Tester: Anuj Patel
Editorialist: Ayesha Uzma

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Math, Observation

PROBLEM:

Lately, a lot of pokemon were brought into the Pokemon Center. So Nurse Joy decided to train her pokemon- Chansey and Bellossom for emergencies.

They were given the initial HP (i) of the patient and the final HP (f) that the patient should have after their recovery. Chansey and Bellossom alternate turns and perform one healing operation in each turn. Chansey heals first. A pokemon wins this training if i=f after performing certain healing operations.

A healing operation can be defined as:

  1. Select an integer x (1< x\leq \frac{i}{2}) and an integer y (1\leq y< x)

  2. Update i as: i= i + (x-y)

Both Chansey and Bellossom heal optimally. Help Nurse Joy declare the winner of the training.

EXPLANATION:

Let us first try to observe what each operation does. Let i be the initial HP, then x ranges from [2,i/2] and y ranges from [1,i/2-1]. Observing carefully, x-y will always range from [1,i/2-1]. This is because, the maximum value x can have after subtraction is i/2-1(max value of x – min value of y). Similarly the minimum value x can have after subtraction is 1(min value of x – min value of y).

Now let us try to understand the problem with an example, where i =7 and f= 15.

We will try to think backwards!

If a pokemon reaches 15, it wins the contest. Therefore we can mark 15 as the winning state. Now what is the minimum value from which the pokemon can reach 15? The minimum value is 11. If the HP values are 11,12,13 or 14 it will win by reaching 15. Therefore [11,15] are winning states. But if the HP value is 10, they must land on 11,12,13,14 which ensures that the opponent wins in the next step. Therefore 10 is a losing state. So we try to find whether i=7 is a winning or a losing state. If i=7 is a winning state then Chansey wins, else it loses.

If f=15 is the final HP, the losing state is ceil(2*(f+1)/3)-1 = 10. Then we can find the losing state for 10, which is 7. Since 7 is a losing state, Chansey loses.

Formula:

Let m be the minimum HP from which we can reach f. From m, the max HP that can obtained after performing the operation is m+((m/2)-1), which is equal to f.

m+((m/2)-1)=f

(3*m)/2=f+1

m=2*(f+1)/3

Therefore we can reach f from 2*(f+1)/3. Hence the losing state is given as 2*(f+1)/3 -1.

SOLUTION:

Setter's Solution
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define endl "\n"
    #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
 
    ll inline ceil(const ll x, const ll y){return ((x/y)+((x%y)!=0));}
 
    int main(){
 
        fast_io
        int t;
        cin>>t;
        while(t--)
        {
            ll i,f;
            cin>>i>>f;
            while(i<f)
            {
                f=ceil(2*(f+1),3)-1;
                //cout<<f<<endl;
            }
            if(i==f)
                cout<<"Bellossom"<<endl;
            else
                cout<<"Chansey"<<endl;
 
            cout.flush();
        }
 
        return 0;
    }