Chef and Walk - RECNDNUM CodeChef Easy Question

Welcome to the knights programming blog .

Here is the link today's problem - PROBLEM

So the problem is to find the time taken for chef to arrive at x=N for the kth time .

So , if you find the pattern by counting , the solution is fairly simple.

You arrive at a direct formula by simple logic and observing the pattern of answer for various k and same x.

So , the formula is different for 0 and all other numbers as time to arrive at 0 for first time is 0 .

Now for other numbers , the formula is split into two parts , k is even or k is odd , this is due to the fact that he arrives at x for kth time while going to another number of coming back from it and hence we get the answer.

Do look at the following C++ code and the formula in it for better understanding .

Code :-

#include <iostream>

using namespace std;

unsigned long long int mod=1000000007;

unsigned long long int power(unsigned long long int x, unsigned long long int y) 

{ 

    if (y == 0) 

        return 1; 

    else if (y % 2 == 0) 

        return power(x, y / 2) * power(x, y / 2)%mod; 

    else

        return x * power(x, y / 2) * power(x, y / 2)%mod; 

} 

int main() {

    long long int t;

    cin>>t;

    while(t--)

    {

        unsigned long long int n,k,x;

        unsigned long long int ans;

        cin>>n>>k;

        if(n==0)

        {

            ans=k*(k-1)%mod;

            cout<<ans<<endl;

            continue;

        }

        if(k%2==1)

        {

            k=k/2;

            x=(n+k)%mod;

            ans=power(x,2)%mod;

            ans=(ans+k)%mod;

        }

        else

        {

            k=k/2;

            x=(n+k)%mod;

            ans=power(x,2)%mod;

            if(ans>=k)

            {

                ans=(ans-k)%mod;

            }

            else

            {

                ans=ans+mod;

                ans=ans-k;

            }

        }

        cout<<ans<<endl;

    }

// your code goes here

return 0;

}

Do leave your doubts and queries in the comments section .