# Chef Anup | codechef solution

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 NK 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.

• For 20 points : N = 32 ≤ K ≤ 1021 ≤ L ≤ 106
• For 30 points : 1 ≤ N ≤ 1022 ≤ K ≤ 1021 ≤ L ≤ 104
• For 50 points : 1 ≤ N ≤ 1032 ≤ K ≤ 1031 ≤ L ≤ 1018

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";
}

}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-