Non Decreasing Digits

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

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.
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 non-decreasing digits.

Resource: ACM Greater New York Regionals 2010

-- Deb

Options

exec is denied

now post-mortem time, all source codes will be revealed

Sample input:_

64
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
63 64
64 1

Sample output:

1 55
2 220
3 715
4 2002
5 5005
6 11440
7 24310
8 48620
9 92378
10 167960
11 293930
12 497420
13 817190
14 1307504
15 2042975
16 3124550
17 4686825
18 6906900
19 10015005
20 14307150
21 20160075
22 28048800
23 38567100
24 52451256
25 70607460
26 94143280
27 124403620
28 163011640
29 211915132
30 273438880
31 350343565
32 445891810
33 563921995
34 708930508
35 886163135
36 1101716330
37 1362649145
38 1677106640
39 2054455634
40 2505433700
41 3042312350
42 3679075400
43 4431613550
44 5317936260
45 6358402050
46 7575968400
47 8996462475
48 10648873950
49 12565671261
50 14783142660
51 17341763505
52 20286591270
53 23667689815
54 27540584512
55 31966749880
56 37014131440
57 42757703560
58 49280065120
59 56672074888
60 65033528560
61 74473879480
62 85113005120
63 97082021465
64 10

Ranking

Ruby _

Perl _

Python _

Scheme _

Common LISP _

Arc _

JavaScript _

BASIC _

J _

C _

OCaml _

Pascal _

Fortran _

COBOL _

Maxima _

AWK _

GolfScript _

gs2 _

Groovy _

Logo _

Language Ranking_

return to the top page