CURSERECURSION - Curse the Recursion

Given the value of n, find the kth number in the sequence produced by the code below.

    void fun(int n)
    {
        if(n>0)
        {
            fun(n-1);
            printf("%d ",n);
            fun(n-1);
        }
    }

Input

First line contains T (number of test-cases, 1 ≤ T ≤ 105)

Next T lines contains two space separated integers n (1 ≤ n ≤ 1018) and k (1 ≤ k ≤ 1018)

Output

For each test-case, print an integer representing the kth number in sequence if it exists otherwise print 0

Example

Input:
5
2 1
2 10
5 4
5 1
5 2

Output:
1
0
3
1
2

Added by:Prakash Jha
Date:2019-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource: Algorithm Theory Class

hide comments
2020-02-24 23:50:25
Zero combinatorics involved, otherwise a very good tutorial problem. Find the pattern & generalize; fun without a need for any algorithm from the book.

TL is fine, pure Python passes in fraction of it and C can get under 0.05s with standard I/O routines.
2019-07-20 12:01:52
using O(logN) algorithm still TLE, i think time limit is too small to handle such large number of Test Cases

Last edit: 2019-07-20 13:21:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.