NY10E  NonDecreasing Digits
A number is said to be made up of nondecreasing digits if all the digits to the left of any digit is less than or equal to that digit.For example, the fourdigit number 1234 is composed of digits that are nondecreasing. Some other fourdigit numbers that are composed of nondecreasing digits are 0011, 1111, 1112, 1122, 2223. As it turns out, there are exactly 715 fourdigit numbers composed of nondecreasing digits.
Notice that leading zeroes are required: 0000, 0001, 0002 are all valid fourdigit numbers with nondecreasing digits.
For this problem, you will write a program that determines how many such numbers there are with a specified number of digits.
Input
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number of digits N, (1 ≤ N ≤ 64).
Output
For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of N digit values that are composed entirely of nondecreasing digits.
Example
Input:
3
1 2
2 3
3 4
Output:
1 55
2 220
3 715
hide comments
lnxdx:
20191004 15:25:20
AC in three goes :\ 

sanket17:
20190806 09:51:53
two things to take care


dkkv0000:
20190511 11:31:31
excellent problem must do for beginners like me took 3hrs but worth it 

ayushgupta1997:
20190211 18:28:41
start from the left most digit, and try and build the possible recursion tree of possibilities, you will find a pattern then, turn the pattern into a 2D dp, precomputation matrix. Last edit: 20190211 18:29:10 

sauravraj62:
20181110 06:03:31
why so weird output format... it costs 2 WA!!! 

jmr99:
20181030 08:43:20
1.'spoiler' will do the job


ankit1cool:
20180614 14:39:54
Remember to use long long costed me 1wa 

spojabhi:
20171217 17:18:10
"OEIS" best site for getting sequences.


vishesh197:
20170926 15:04:03
simple problem.... just use dp and long long and state of dp as dp(last digit chosen,number of digits).AC in 1st go... 

code_aim:
20170904 15:52:59
100th 
Added by:  John Mario 
Date:  20110322 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM Greater New York Regionals 2010 