# Chef and Riffles RIFFLES Solution Codechef

Page Contents

## Codechef Chef and Riffles RIFFLES Solution

Let ff be a permutation of length NN, where NN is even. The riffle of ff is defined to be the permutationg=(f(1),f(3),…,f(N−1),f(2),f(4),…,f(N))g=(f(1),f(3),…,f(N−1),f(2),f(4),…,f(N))

You are given two integers NN and KK. Output the resultant permutation when you riffle the identity permutation of length NN, KK times.

The identity permutation of length NN is σN=(1,2,…,N)σN=(1,2,…,N)

### Input Format

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• Each test case consists of a single line of input, containing two space-separated integers NN and KK.

### Output Format

For each test case, output the answer permutation as NN space-separated integers in a new line.

### Constraints

• 1≤T≤1001≤T≤100
• 1≤N≤3⋅1051≤N≤3⋅105
• 1≤K≤1091≤K≤109
• NN is even
• The sum of NN across test cases does not exceed 3⋅1053⋅105

• Subtask 1 (30 points): NN is a power of 22
• Subtask 2 (70 points): Original constraints

```3
6 1
8 2
14 452```

### Sample Output 1

```1 3 5 2 4 6
1 5 2 6 3 7 4 8
1 10 6 2 11 7 3 12 8 4 13 9 5 14```

### Explanation

Test case 11: Performing the riffle on σ6=(1,2,3,4,5,6)σ6=(1,2,3,4,5,6) once results in (1,3,5,2,4,6)(1,3,5,2,4,6), by definition.

Test case 22: The process goes as follows:

• Performing the riffle on (1,2,3,4,5,6,7,8)(1,2,3,4,5,6,7,8) results in (1,3,5,7,2,4,6,8)(1,3,5,7,2,4,6,8)
• Performing the riffle on (1,3,5,7,2,4,6,8)(1,3,5,7,2,4,6,8) results in (1,5,2,6,3,7,4,8)(1,5,2,6,3,7,4,8)

## Solution

Program: Chef and Riffles RIFFLES Solution in C++

```#include <iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
vector<int>v(n+1);
int arr[n+1][31];
int j=1;
for(int i=1;i<=n;i+=2)
arr[i][0]=j++;
for(int i=2;i<=n;i+=2)
arr[i][0]=j++;
for(int j=1;j<=30;j++)
{
for(int i=1;i<=n;i++)
arr[i][j]=arr[arr[i][j-1]][j-1];
}
vector<int>a(n+1);
for(int j=1;j<=n;j++)
{
int temp=k;
int p=j;
for(int i=0;i<=30;i++)
{
if(1<<i&temp)
p=arr[p][i];
}
a[p]=j;
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<'\n';
}
}```

Program: Chef and Riffles RIFFLES Solution in Java

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

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int t = 0; t < T; t++) {
int N = in.nextInt(), K = in.nextInt();
int[][] jump = new int[N][32];
for (int i = 0; i < N / 2; i++) {
jump[i * 2][0] = i;
jump[i * 2 + 1][0] = N / 2 + i;
}
for (int j = 1; j < 32; j++) {
for (int i = 0; i < N; i++) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
int[] res = new int[N];
for (int i = 0; i < N; i++) {
int current = i;
int n = K, j = 0;
while (n > 0) {
if (n % 2 == 1) {
current = jump[current][j];
}
n >>= 1;
j++;
}
res[current] = i;
}
for (int i = 0; i < N; i++) {
System.out.print((res[i] + 1) + (i == N - 1 ? "\n" : " "));
}
}
}
}```

Program: Chef and Riffles RIFFLES Solution in Python

```for _ in range(int(input())):
a,b = map(int,input().split())
a = [0] * a
c = 1
no=(len(a)//2)+1
while(no!=2):
if(no%2==1):
no = (no//2)+1
else:
no = (no+len(a))/2
c+=1
b = b%c

for i in range(c-b-1):
else:
a[0] = 1
for i in range(1,len(a)):
if(new>len(a)):
a[i] = (new%len(a))+1
else:
a[i] = new
for i in a:
print(i,end=" ")
print()```