Header Ads Widget

Climbing Stairs | codechef solution

Rajnish Tripathi 23:07

 Problem :-

There is a ritual that some monks of Byteland perform every century as a sign of respect and worship towards BOOL, the God of Byteland.

All the monks train for many years in order to accomplish an extremely hard task, that is the one of accessing the sacred temple of Byteland, where only the best of the bests monks are allowed to enter and worship their god, BOOL.

The training the monks perform, usually consists of several physically and intellectually challenging tasks, trained and perfected over the course of many years, so that one of them can be eligible for the ultimate task that is a combination of both physical effort as well as mental effort.

This final task is the actual possibility of trying to access the sacred temple of Byteland, that is located on the top of a very high mountain, where reckless storms and heavy rains usually occur.

The access to this mountain is done by climbing an enourmous set of stairs that spiral around the mountain until it ends on the top of the mountain where the sacred temple door is located.

The door can only be opened by unlocking it. To unlock the door, the monk only sees a hole in it, a lever, and he also spots a very large amount of little round stones on the ground, and he understands that the only way to open the door is to place an exact pre-determined amount of stones trough that hole, so that when the number is correct, he will push the lever down, and the door will open. If this number is incorrect, the lever will be locked by the incorrect stones and a whole new century must pass so that the storms can erode the stones and a new monk can be selected for the task.

This year, YOU were the one selected to climb the huge set of stairs, and you are extremely well prepared... You have done your training very well and you are also aware of two very important facts that will be key for your success... The favourite number base on Byteland is base 2, and Gods favourite number is the largest number on this base. You also know that the number of stones you need to place on the door hole is related to the way everyone climbs the stairs and with the number of stairs itself.

As the monks take several supplies for the demanding trip, they can only climb either one or two steps at a time. You understood that the number of stones you need to place on the door is closely related with the way you climb the stairs. Suppose the number of stairs you need to climb is N. Also, let the number of ways you have of climbing those N stairs be M. Now, the number of stones required is equal to the number of 1's in the base-2 representation of (M modulo 1000000007).

You won't fail, as you are extremely well ready, but you have made everyone on your town extremely excited with your journey, so, given the number N of steps you are to climb and a guess, G, from the people of your village, you need to see if they are correct or not.

More formally, given a number N of steps to climb and a guess G from your village, you need to check if guess G is accordingly to your correct calculations. They are correct if you manage to enter the temple using their guess, or incorrect otherwise. You should output the string “CORRECT” if they are correct, or “INCORRECT” if they are incorrect. (Quotes for clarity only). Please read the section "Output Explanation" for some clarification on the example cases.

Input

The first line of each official test case file will contain an integer T, that stands for the number of test cases on that specific test case file. The next T lines contain two-space separated integers, N and G, respectively, the number of steps the monk needs to climb and the guess from the village's population.

Output

Output will contain the string "CORRECT" or "INCORRECT" on a single line, as explained above on the problem statement.

Constraints

In each file, T = 100000, i.e., each file will contain 100000 test cases (this value needs to be read from standard input).

1 ≤ N ≤ 1000000

0 ≤ G ≤ 50

Your code will be judged against several input files.

Example

Input:
100000
1 1
7 4
(and 99998 more test cases...)

Output:
CORRECT
INCORRECT
(and 99998 more answers...)

Output Explanation:

On the first case, when there is only one step to climb, there is only one way to do it. 1 in binary is 1, and as the village's population guess is also 1 the answer is correct.

On the second case, there are 21 ways of climbing the stairs altogether. 21 in binary is 10101, that contains three ones. As the village's population guess was 4, the answer is therefore incorrect.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
const int a=1e9+7;
int main() {
int t;
cin>>t;
vector<int >vec(1000001,0);
vec[0]=0;
vec[1]=1;
vec[2]=2;
for(int i=3;i<1000000;i++){
vec[i]=(vec[i-1]+vec[i-2])%a;
}
while(t--){
int n,k;
cin>>n>>k;
int x=log2(vec[n])+1;
bitset<32>bit(vec[n]);
int cr=bit.count();
if(cr==k){
cout<<"CORRECT"<<endl;
}
else{
cout<<"INCORRECT"<<endl;
}
}
    return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        long a[]=new long[1000001];
         a[0]=1;
         a[1]=1;
         for (int i=2;i<=1000000 ;i++ ){
         a[i]=(a[i-1]%1000000007+a[i-2]%1000000007)%1000000007;
         }
        while(t-->0){
         long n=sc.nextLong();
         int g=sc.nextInt();
         long x=a[(int)n];
         int count=0;
         while(x>0){
         if((x&1)==1)
         count++;
         x=x>>1;
         }
         if(count==g)
         System.out.println("CORRECT");
         else
         System.out.println("INCORRECT");
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-



Tags:

Post a Comment

0 Comments