GNYR04C  Lennys Lucky Lotto Lists
Lotto is a lottery, typically with an accumulating jackpot, in which participants play numbers of their choice in a random drawing. Lenny likes to play the lotto in Lincoln county Louisiana. In the game, he picks a list of n numbers in the range from 1 to m. If his list matches the drawn list, he wins the big prize, a lifetime supply of large lemons.
Lenny has a scheme that he thinks is likely to be lucky. He likes to choose his list so that each number in it is at least twice as large as the one before it. So, for example, if n = 4 and m = 10, then the possible lucky lists Lenny could pick are:
1 2 4 8 1 2 4 9 1 2 4 10 1 2 5 10
Thus Lenny has 4 lists to choose from.
Your job, given n and m, is to count how many lucky lists Lenny has to his disposal.
Input
The first line of input is a single nonnegative integer, which is the number of data sets to follow. All data sets should be handled identically. The next lines, one per data set, contain two integers, nand m. It is guaranteed that 1 <= n <= 10 and 1 <= m <= 2000 and n <= m.
Output
For each data set, print a line like the following:
Data set i: n m number
where i is the data set number (beginning with 1), and number is the maximum number of lucky lists corresponding to the provided values of n and m.
Example
Input
1 4 10
Output
Data set 1: 4 10 4
hide comments
nadstratosfer:
20171028 04:13:19
Beware of blanklines in input. 

Sigma Kappa:
20170819 23:42:34
Speaking of DP, why it is that when I click on the "#DynamicProgramming" tag I always end up with the same list which, for example, does not have this particular task in it? And when the "Comingsoon" feature of SPOJ will indeed come? 

vengatesh15:
20170207 13:16:48
dp:) 

ashish22_dwd:
20160913 20:47:42
Yesss.. Nice trick :) 

Naman Goyal:
20150526 18:02:08
Result requires and fits in 8 byte. Doesn't fit in 4 byte. 

pingal tirkey:
20150524 08:21:45
DP :) 

shikhar jindal:
20150415 18:40:29
anyone please provide me with some tricky test cases.. 

Apoorv Jindal:
20131216 18:04:02
O(10*2000+t) :) Last edit: 20131216 18:04:30 

albertg:
20130922 15:46:01
O(n*m+t) 

Vedernikoff Sergey:
20130823 13:14:56
O(10 * 2000 + #testcases) for all testcases 
Added by:  abdelkarim 
Date:  20130813 
Time limit:  0.666s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM Regionals 2004 North America  Greater NY 