Header Ads Widget

Chef and Ridges | codechef solution

Rajnish Tripathi 04:30

 Problem:-

###Read problems statements Hindi , Vietnamese , Mandarin Chinese , Russian and Bengali as well.

We have a rectangular piece of cardboard with width 1 (its height is not important). We are going to fold it in the following way:

  • pick up the right side of the piece of cardboard and move it to the left until it touches the left side
  • this way, a smaller piece of cardboard with width 1/2 is created; if we unfolded it, we could see a vertical ridge formed in the middle
  • pick up the left side of this new piece of cardboard and move it to the right until it touches the (new) right side
  • pick up the right side of the resulting piece of cardboard and move it to the left until it touches the left side, etc.

Whenever the cardboard is folded, exactly one of its new sides is a newly formed ridge (there may be more, internal ridges formed, but we do not consider these). Let's denote such a ridge created in the �-th folding by ��.

In total, we fold the piece of cardboard � times. Afterwards, we unfold it and look at the formed ridges. Let's denote the distance of ridge �� (i.e. the last formed outer ridge) from the left side of the original piece of cardboard by ��. For example, �1=1/2 and �2=1/4.

It is possible to express �� as an irreducible fraction �/�. Find this fraction.

Assume that it is possible to fold the piece of cardboard as many times as we want.

Input

The first and only line of the input contains a single integer � denoting the number of test cases. For each test case, a space and an integer � follows.

Output

Print a single line containing 2� space-separated integers. For the �-th test case (1≤�≤�), the 2�−1-th and 2�-th integer should denote � and � — the position of the last ridge as an irreducible fraction.

Constraints

  • 1≤�≤5
  • 1≤�≤25

Subtask #1 (10 points):

  • 1≤�≤5
  • 1≤�≤5

Subtask #2 (90 points): original constraints

Sample 1:

Input
Output
2 1 2
1 2 1 4

Explanation:

Example case 1: We only fold once, so �=1 and �=2.

Example case 2: We fold the piece of cardboard twice. The last edge is at 1/4, so �=1 and �=4.

Code(C++):-

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

int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T, N; cin >> T;
while(T--) {
cin >> N;
int num = 0, denum = 1, width;
for(int n = 1; n<=N; n++) {
num *= 2;
denum *= 2;
if(n%2==1) // fold left
num += 1;
else // fold right
num -= 1;
}
cout << num << ' ' << denum << ' ';
}
cout << endl;
}

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
    {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0){
         int n=sc.nextInt();
         int d=(int)Math.pow(2,n);
         int arr[]=new int[2*n];
         arr[0]=d/2;
         arr[1]=d/4;
         for(int i=2;i<n;i++){
         arr[i]=(arr[i-1]+arr[i-2])/2;
         }
         System.out.print(arr[n-1]+" "+d+" ");
        }
    }
}

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