Small Change

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

On the island of Anarchygolfania they still use coins for all transactions. Each shop only keeps certain denominations of coins. When someone buys something, they always try to give the change back using the smallest number of coins possible. There is no centralized government to dictate what coins are legal tender so each shop uses a coins with different denominations.

The input will consist of one line per transaction. The first number gives the amount of change that must be paid back to the customer. The remaining numbers give the denominations of the coins that the store keeps.

The result should be a single line listing the required coins in increasing order of size. You can use more than one coin of each denomination.

If it is impossible to create the exact amount using only the given coins, return a line containing the hyphen symbol.

As an example, if the allowed coins have values 1, 7 and 12 and you must make the value 14, you should output "7 7". The solution "1 1 12" is not correct because it requires one more coin.

-Mark Byers (mark.byers@gmail.com)

Options

exec is denied

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

Sample input:_

1: 1
2: 1
1: 2
2: 1 2
15: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1111: 1 10 100
13: 1 7 12
14: 1 7 12
20: 1 7 12
12: 1 2 3 4

Sample output:

1
1 1
-
2
15
1 10 100 100 100 100 100 100 100 100 100 100 100
1 12
7 7
1 7 12
4 4 4

Sample input:_

553: 32 35 37 59 64
2741: 86 123 201 287 469 536 623 800 983
3513: 78 482 830 981
2315: 310 415 418 428 463 481 584 645 647
7810: 125 324 555 602 767 856

Sample output:

35 35 35 64 64 64 64 64 64 64
201 287 287 983 983
78 78 78 78 78 482 830 830 981
463 463 463 463 463
125 324 602 767 856 856 856 856 856 856 856

Sample input:_

1970: 129 349 433 469 532 552 724 888 955
2389: 114 210 258 351 658 781 903
5146: 306 489 859 871 873 892
6494: 328 752 830 981
6532: 223 446 493 527 638 704 742 830 878

Sample output:

433 433 552 552
210 210 258 351 351 351 658
306 489 859 873 873 873 873
-
704 704 830 830 830 878 878 878

Ranking

Ruby _

RankUserSizeTimeDateStatistics
1flagitious1100.85032008/10/07 21:58:430B / 42B / 60B
2kinaba1120.76982008/10/13 17:04:550B / 42B / 62B
3ksk1181.69182008/10/13 20:37:090B / 44B / 67B
4shinh1291.24922008/10/07 21:11:230B / 53B / 67B
5MarkByers1451.77592008/10/08 11:49:440B / 56B / 80B
6leonid2271.75132008/10/07 06:07:180B / 103B / 86B

Python _

RankUserSizeTimeDateStatistics
1MarkByers1771.52182008/10/12 00:36:470B / 83B / 81B
2recursive1902.02812008/10/07 05:28:570B / 93B / 77B
3hirose2171.59962008/10/10 14:13:480B / 103B / 83B

Common LISP _

RankUserSizeTimeDateStatistics
1kozima3371.05012008/10/09 09:23:110B / 178B / 124B
2kozima3242.55462008/10/14 08:51:020B / 174B / 118B

JavaScript _

RankUserSizeTimeDateStatistics
1nn1590.98442008/10/08 11:58:430B / 75B / 81B
2murky-satyr1511.62372008/10/14 06:02:010B / 63B / 87B

J _

RankUserSizeTimeDateStatistics
1I., S.1341.27432011/11/28 07:03:010B / 26B / 104B

C _

RankUserSizeTimeDateStatistics
151b2360.10822008/10/13 19:10:460B / 102B / 134B
2hinoe2360.09912008/10/13 20:29:420B / 106B / 130B

D _

RankUserSizeTimeDateStatistics
151b2500.15792009/01/26 00:38:010B / 123B / 123B

Haskell _

RankUserSizeTimeDateStatistics
1fox1940.20092008/10/11 14:52:230B / 100B / 72B
2fox1930.14112008/10/14 14:28:480B / 100B / 71B

AWK _

RankUserSizeTimeDateStatistics
1nn1070.70152008/10/08 14:24:370B / 49B / 57B

sed _

RankUserSizeTimeDateStatistics
1eban3680.04762008/10/07 01:13:340B / 247B / 25B

Bash _

RankUserSizeTimeDateStatistics
1eban1870.16092008/10/07 02:06:1681B / 71B / 27B

Postscript _

RankUserSizeTimeDateStatistics
1yshl(bin)1851.82972008/10/11 18:42:0385B / 49B / 49B
2yshl3241.71892008/10/11 18:42:130B / 227B / 51B

goruby _

RankUserSizeTimeDateStatistics
1murky-satyr970.34212010/01/04 17:44:550B / 33B / 57B

Groovy _

RankUserSizeTimeDateStatistics
1murky-satyr1644.88802009/12/02 11:08:310B / 80B / 78B
2nn1814.36122009/11/20 07:37:130B / 89B / 81B

Language Ranking_

RankLangUserSizeScore
1gorubymurky-satyr9710000
2AWKnn1079065
3Rubyflagitious1108818
4JI., S.1347238
5JavaScriptmurky-satyr1516423
6Groovymurky-satyr1645914
7PythonMarkByers1775480
8Postscriptyshl(bin)1855243
9Basheban1875187
10Haskellfox1935025
11C51b2364110
12D51b2503880
13Common LISPkozima3242993
14sedeban3682635

return to the top page