NY10E - Non-Decreasing Digits
A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.For example, the four-digit number 1234 is composed of digits that are non-decreasing. Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223. As it turns out, there are exactly 715 four-digit numbers composed of non-decreasing digits.
Notice that leading zeroes are required: 0000, 0001, 0002 are all valid four-digit numbers with non-decreasing digits.
For this problem, you will write a program that determines how many such numbers there are with a specified number of digits.
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).
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 non-decreasing digits.
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: 2019-02-11 18:29:10
why so weird output format... it costs 2 WA!!!
1.'spoiler' will do the job
Remember to use long long costed me 1wa
"OEIS" best site for getting sequences.
simple problem.... just use dp and long long and state of dp as dp(last digit chosen,number of digits).AC in 1st go...
wow.. a good combinatorics problem!.. pure maths :)
Easy AC in one GO..!! O(n*10) java- 0.04s
Easy dp. Just think for 20 minutes and write if you are not getting.