Non Decreasing Digits

Submit

Your name:
File:
Open code-statistics:

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 _

RankUserSizeTimeDateStatistics
1leonid500.01722011/04/20 11:00:560B / 25B / 22B

Perl _

RankUserSizeTimeDateStatistics
1tails450.00192011/04/20 04:49:470B / 16B / 29B
2teebee460.01742011/04/24 17:18:100B / 18B / 25B

Python _

RankUserSizeTimeDateStatistics
1leonid530.03012011/04/20 11:07:440B / 31B / 18B
2hallvabo530.03192011/04/30 05:58:030B / 31B / 21B
3recursive620.02622011/04/20 22:54:192B / 38B / 16B

Scheme _

RankUserSizeTimeDateStatistics
1youz780.04102011/04/28 18:23:090B / 30B / 39B
2kaki780.07592011/04/29 06:24:020B / 36B / 35B
3kaki750.01862013/03/25 06:47:330B / 31B / 40B

Common LISP _

RankUserSizeTimeDateStatistics
1kozima690.51322011/04/28 11:08:150B / 32B / 32B
2youz690.05652011/04/28 18:22:310B / 32B / 32B

Arc _

RankUserSizeTimeDateStatistics
1youz631.99272011/04/28 18:22:260B / 23B / 31B

JavaScript _

RankUserSizeTimeDateStatistics
1nn660.00042011/04/30 00:03:010B / 32B / 34B

BASIC _

RankUserSizeTimeDateStatistics
1*yuko*560.00302011/04/24 12:33:440B / 35B / 18B

J _

RankUserSizeTimeDateStatistics
1pooq410.04352011/04/19 15:53:070B / 15B / 25B
2I., S.(pooq)(devious)290.06132011/05/10 20:31:450B / 13B / 16B
3I., S.(pooq)300.05342011/05/07 12:15:510B / 14B / 15B
4I., S.350.04752011/05/07 09:50:210B / 13B / 22B

C _

RankUserSizeTimeDateStatistics
1nn850.00032011/04/25 22:37:490B / 45B / 38B
2Debanjan (Testing)7640.00092011/04/19 05:17:248B / ?B / ?B

OCaml _

RankUserSizeTimeDateStatistics
1m.ukai1340.04782011/04/19 19:34:110B / 67B / 54B

Pascal _

RankUserSizeTimeDateStatistics
1*yuko*960.00042011/04/24 12:25:100B / 65B / 24B

Fortran _

RankUserSizeTimeDateStatistics
1*yuko*790.00042011/04/24 12:04:490B / 51B / 27B
2*yuko*760.01282011/12/03 01:17:410B / 48B / 26B

COBOL _

RankUserSizeTimeDateStatistics
1*yuko*2180.00272011/04/24 13:41:340B / 151B / 40B

Maxima _

RankUserSizeTimeDateStatistics
1pooq590.20152011/04/19 07:20:130B / 28B / 29B

AWK _

RankUserSizeTimeDateStatistics
1hemflit510.00142011/04/21 00:59:580B / 21B / 30B

GolfScript _

RankUserSizeTimeDateStatistics
1nooodl330.08262011/04/22 20:17:240B / ?B / ?B

Groovy _

RankUserSizeTimeDateStatistics
1nn612.37222011/04/25 22:41:070B / 34B / 24B

Logo _

RankUserSizeTimeDateStatistics
1teebee460.13732011/04/21 04:40:120B / 28B / 13B

Language Ranking_

RankLangUserSizeScore
1JI., S.(pooq)(devious)2910000
2GolfScriptnooodl338787
3Perltails456444
4Logoteebee466304
5Rubyleonid505800
6AWKhemflit515686
7Pythonleonid535471
8BASIC*yuko*565178
9Maximapooq594915
10Groovynn614754
11Arcyouz634603
12JavaScriptnn664393
13Common LISPkozima694202
14Schemekaki753866
15Fortran*yuko*763815
16Cnn853411
17Pascal*yuko*963020
18OCamlm.ukai1342164
19COBOL*yuko*2181330

return top