Small Change
Submit
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
Rank | User | Size | Time | Date | Statistics |
---|
1 | flagitious | 110 | 0.8503 | 2008/10/07 21:58:43 | 0B / 42B / 60B |
2 | kinaba | 112 | 0.7698 | 2008/10/13 17:04:55 | 0B / 42B / 62B |
3 | ksk | 118 | 1.6918 | 2008/10/13 20:37:09 | 0B / 44B / 67B |
4 | shinh | 129 | 1.2492 | 2008/10/07 21:11:23 | 0B / 53B / 67B |
5 | MarkByers | 145 | 1.7759 | 2008/10/08 11:49:44 | 0B / 56B / 80B |
6 | leonid | 227 | 1.7513 | 2008/10/07 06:07:18 | 0B / 103B / 86B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | MarkByers | 177 | 1.5218 | 2008/10/12 00:36:47 | 0B / 83B / 81B |
2 | recursive | 190 | 2.0281 | 2008/10/07 05:28:57 | 0B / 93B / 77B |
3 | hirose | 217 | 1.5996 | 2008/10/10 14:13:48 | 0B / 103B / 83B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | kozima | 337 | 1.0501 | 2008/10/09 09:23:11 | 0B / 178B / 124B |
2 | kozima | 324 | 2.5546 | 2008/10/14 08:51:02 | 0B / 174B / 118B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | nn | 159 | 0.9844 | 2008/10/08 11:58:43 | 0B / 75B / 81B |
2 | murky-satyr | 151 | 1.6237 | 2008/10/14 06:02:01 | 0B / 63B / 87B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | I., S. | 134 | 1.2743 | 2011/11/28 07:03:01 | 0B / 26B / 104B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | 51b | 236 | 0.1082 | 2008/10/13 19:10:46 | 0B / 102B / 134B |
2 | hinoe | 236 | 0.0991 | 2008/10/13 20:29:42 | 0B / 106B / 130B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | 51b | 250 | 0.1579 | 2009/01/26 00:38:01 | 0B / 123B / 123B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | fox | 194 | 0.2009 | 2008/10/11 14:52:23 | 0B / 100B / 72B |
2 | fox | 193 | 0.1411 | 2008/10/14 14:28:48 | 0B / 100B / 71B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | nn | 107 | 0.7015 | 2008/10/08 14:24:37 | 0B / 49B / 57B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | eban | 368 | 0.0476 | 2008/10/07 01:13:34 | 0B / 247B / 25B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | eban | 187 | 0.1609 | 2008/10/07 02:06:16 | 81B / 71B / 27B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | yshl(bin) | 185 | 1.8297 | 2008/10/11 18:42:03 | 85B / 49B / 49B |
2 | yshl | 324 | 1.7189 | 2008/10/11 18:42:13 | 0B / 227B / 51B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | murky-satyr | 164 | 4.8880 | 2009/12/02 11:08:31 | 0B / 80B / 78B |
2 | nn | 181 | 4.3612 | 2009/11/20 07:37:13 | 0B / 89B / 81B |
Language Ranking_
Rank | Lang | User | Size | Score |
1 | goruby | murky-satyr | 97 | 10000 |
2 | AWK | nn | 107 | 9065 |
3 | Ruby | flagitious | 110 | 8818 |
4 | J | I., S. | 134 | 7238 |
5 | JavaScript | murky-satyr | 151 | 6423 |
6 | Groovy | murky-satyr | 164 | 5914 |
7 | Python | MarkByers | 177 | 5480 |
8 | Postscript | yshl(bin) | 185 | 5243 |
9 | Bash | eban | 187 | 5187 |
10 | Haskell | fox | 193 | 5025 |
11 | C | 51b | 236 | 4110 |
12 | D | 51b | 250 | 3880 |
13 | Common LISP | kozima | 324 | 2993 |
14 | sed | eban | 368 | 2635 |
return to the top page