Header Ads Widget

Chef Anup | codechef solution

Rajnish Tripathi 11:20

Chef Anup is making dishes. Each dish consists of N ingredients, and quantity of each ingredient is an integer between 1 and K inclusive.

Relative quality of 2 dishes is determined by their lexicographic order. Dish A is of lower quality than dish B if there is a position i (1<=i<=N) such that Aj = Bj for all j < i and Ai < Bi.
E.g., if N = 2 and K = 2, then the possible dishes in lexicographic order are (1,1), (1,2), (2,1), (2,2).

Given an integer L, determine the Lth possible dish in increasing order of quality.

Input Format

  • The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
  • Each test case description consists of a single line containing three integers N, K and L as described above.

Output Format

  • For each test case, print N space-separated integers in a single line describing the quantities of the ingredients for the Lth dish.

Constraints

  • 1 ≤ T ≤ 10
  • L will not exceed the total number of possible dishes.

Subtasks

  • For 20 points : N = 3, 2 ≤ K ≤ 102, 1 ≤ L ≤ 106
  • For 30 points : 1 ≤ N ≤ 102, 2 ≤ K ≤ 102, 1 ≤ L ≤ 104
  • For 50 points : 1 ≤ N ≤ 103, 2 ≤ K ≤ 103, 1 ≤ L ≤ 1018

Sample 1:

Input
Output
4
3 3 1
3 3 2
3 3 3
3 3 4
1 1 1
1 1 2
1 1 3
1 2 1

Explanation:

First 4 dishes in order have ingredients (1,1,1), (1,1,2), (1,1,3), and (1,2,1).

Sample 2:

Input
Output
4
4 3 1
4 3 2
4 3 3
4 3 4
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1

Explanation:

First 4 dishes in order have ingredients (1,1,1,1), (1,1,1,2), (1,1,1,3), and (1,1,2,1).

 Code(C++):-

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

int main()
{
    int t;
    cin>>t;
    while(t--)
{
    long long int n,k,l;
    cin>>n>>k>>l;
    vector<int>arr;
long long int temp=l-1;
while(temp>0)
{
int rem=temp%k;
arr.push_back(rem);
temp=temp/k;
}
for(int i=0;i<n;i++){
if(i<arr.size())
arr[i]+=1;
else
arr.push_back(1);
}
for(int i=arr.size()-1;i>=0;i--)
cout<<arr[i]<<" ";
cout<<"\n";
}
    
}

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. */
public class Main
{
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(
new InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try {
if(st.hasMoreTokens()){
str = st.nextToken("\n");
}
else{
str = br.readLine();
}
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}

    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        FastReader sc = new FastReader();
        int t = sc.nextInt();
        for (int cnt=0; cnt<t; cnt++)
        {
         long n = sc.nextLong();
         long k = sc.nextLong();
         long p = sc.nextLong()-1;
         for (long i=n-1; i>=0; i--)
         {
         long d = (long)(Math.pow(k,i));
         long e = (p/d)%k;
         System.out.print(e + 1 + " ");
         }
         System.out.println();
        }
    }
}

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