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

quantic:
20170701 18:27:51
wow.. a good combinatorics problem!.. pure maths :) 

da_201501181:
20170606 09:35:52
Easy AC in one GO..!! O(n*10) java 0.04s 

cj23897:
20170603 08:32:48
Easy dp. Just think for 20 minutes and write if you are not getting. 
Added by:  John Mario 
Date:  20110322 
Time limit:  0.166s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM Greater New York Regionals 2010 