TopCoder Statistics - Problem Statement

Problem Statement

The Change-O-Matic is a deterministic machine with a single goal: to provide change. That is, you throw in a banknote or a coin, and the machine throws out a bunch of smaller coins with the same total value.

More precisely, the Change-O-Matic operates as follows:

The machine contains several large stacks of coins. The values of these coins are given as a int[] outputValues. For the purpose of this problem we may assume that the machine contains an infinite number of coins of each of these values. One of the available values is always 1.

The customer may throw in any coin or banknote with value greater than 1. The machine will output a set of at least two coins with the same total value. If there are multiple ways to satisfy this requirement, the machine prefers the one where the total number of output coins is minimized. If there are still multiple ways, the machine prefers the one that is lexicographically maximal (see Notes for a precise definition).

You have a single banknote, and its value is given as a long inputValue. You would like to change it into coins of value 1 each. Return the number of times you have to throw something into the machine.

Definition

Class:: ChangeOMatic
Method:: howManyRounds
Parameters:: int[], long
Returns:: long
Method signature:: long howManyRounds(int[] outputValues, long inputValue)
(be sure your method is public)

Notes

Let A=(a1,...,aN) and B=(b1,...,bN) be two different but equally large sets of coins, with a1 >= a2 >= ... >= aN and b1 >= b2 >= ... >= bN. Let x be the smallest index such that ax != bx. If ax > bx, we say that the set A is lexicographically larger than the set B.
Given a collection of different but equally large sets of coins, the lexicographically maximal set is the one that is lexicographically larger than each of the other sets. (Note that there is always exactly one such set.)

Constraints

outputValues will contain between 1 and 50 elements, inclusive.
outputValues will be sorted in strictly ascending order. That is, for each i, outputValues[i] < outputValues[i+1].
Each element of outputValues will be between 1 and 1,000, inclusive.
Element 0 of outputValues will be equal to 1.
inputValue will be between 2 and 10^15, inclusive.

Examples

{1,5,10}

21

Returns: 7

The process of changing your money may look as follows: You insert: You get: You then have: 21 10+10+1 10+10+1 10 5+5 10+5+5+1 5 1+1+1+1+1 10+5+1+1+1+1+1+1 10 5+5 5+5+5+1+1+1+1+1+1 5 1+1+1+1+1 5+5+(eleven times 1) 5 1+1+1+1+1 5+(sixteen times 1) 5 1+1+1+1+1 twenty-one coins worth 1 each
{1,33,90,91,92,93,94,95,96,97,98}

99

Returns: 12

In each step, the machine minimizes the number of coins it throws out, not the number of steps you need to accomplish your task. In the first step it will output a coin worth 98 and a coin worth 1.
{1,30,60}

50

Returns: 2

The value of the banknote may be less than the values of some coin types.
{1,30,60,90}

60

Returns: 3

The value of the banknote may even be equal to the value of some coin type. Note that for any input the machine must always output at least two coins. Therefore if you throw in the banknote worth 60, you will get two coins worth 30 each.
{1,8,9,11,12,100}

120

Returns: 37

In the first step the machine would output 100+12+8. (The combination 100+11+9 has the same number of coins, but 100+12+8 is lexicographically larger.)
{1,2}

987654321098765

Returns: 493827160549383
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,64,128,256,512,1000}

987654321098765

Returns: 983703703814369
{1,2,3,4,5,6}

2

Returns: 1
{1}

47

Returns: 1
{1,47}

47

Returns: 1
{1,302,402,595,596,597,598,599,600,601,602}

1206

Returns: 13
{1,302,402,595,596,597,598,599,600,601,602}

6026026021206

Returns: 100100100013
{1,999,1000}

997002

Returns: 999
{1,999,1000}

999999999997002

Returns: 1999999998999
{1,999,1000}

996002

Returns: 1993
{1,997,998,999,1000}

1994

Returns: 3
{1,997,998,999,1000}

322142121994

Returns: 1288568483
{1,90,900,994,995,996,997,998,999,1000}

1980

Returns: 25
{1,89,90,900,994,995,996,997,998,999,1000}

1980

Returns: 47
{1,90,900,994,995,996,997,998,999,1000}

214215499980

Returns: 4070094481
{1,2,4,8,16,32,64,128,256,512,1000}

987658765498765

Returns: 982720471671273
{1,2,3,5,8,13,21,34,55,89,144,233,377,610,987}

987654321154321

Returns: 986653658214953
{1,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1000}

987654321154321

Returns: 48395061735917
{1,5,65,66,67,68,69,70,200,1000}

210

Returns: 51
{1,5,65,66,67,68,69,70,200,1000}

1210

Returns: 292
{1,5,65,66,67,68,69,70,200,1000}

410

Returns: 99
{1,5,70,190,191,192,193,194,195,196,197,198,199,200,1000}

210

Returns: 54
{1,5,70,190,191,192,193,194,195,196,197,198,199,200,1000}

280

Returns: 69
{1,5,70,191,192,193,194,195,196,197,198,199,200,1000}

280

Returns: 68
{1,5,70,191,192,193,194,195,196,197,198,199,200,1000}

4723521100210

Returns: 1185603796153
{1,12,45,57,62,173,192,654,721,854}

9692

Returns: 1021
{1,12,45,57,62,173,192,654,721,854,857}

95648

Returns: 10081
{1,12,45,57,62,173,192,654,721,854,857}

95647

Returns: 10110
{1,12,45,57,62,173,192,654,721,854,857}

956480

Returns: 101549
{1,12,45,57,62,173,192,654,721,849,854,857}

720801

Returns: 77370
{1}

5819977

Returns: 1
{1}

953255819977

Returns: 1
{1, 866}

6

Returns: 1
{1, 230, 789}

510829837730

Returns: 2589758364
{1, 86, 777, 901}

2359803658092

Returns: 31429127513
{1, 146, 225, 330, 719}

434169

Returns: 4225
{1, 21, 367, 563, 731, 987}

914398942265

Returns: 45395692171
{1, 45, 51, 293, 892, 901, 939}

32443435609

Returns: 1209286688
{1, 133, 198, 349, 574, 799, 906, 959}

4418129272051

Returns: 46070169679
{1, 241, 373, 404, 638, 767, 859, 861, 988}

281082551445

Returns: 1706979060
{1, 22, 183, 252, 278, 363, 590, 611, 832, 892}

6700824662

Returns: 353070370
{1, 4, 228, 234, 343, 472, 490, 514, 532, 732, 863}

289451635526422

Returns: 75129972604774
{1, 266, 320, 395, 452, 459, 581, 915, 928, 948, 991, 1000}

2877532

Returns: 25892
{1, 45, 98, 126, 233, 317, 344, 390, 457, 551, 643, 683, 765}

5

Returns: 1
{1, 97, 114, 243, 267, 309, 380, 418, 491, 578, 582, 726, 810, 888}

7753

Returns: 157
{1, 25, 56, 175, 198, 363, 521, 536, 657, 664, 686, 688, 740, 858, 968}

53086129

Returns: 2742044
{1, 182, 317, 344, 367, 389, 445, 481, 619, 680, 779, 782, 806, 853, 927, 968}

61329830700347

Returns: 760287157441
{1, 13, 20, 22, 254, 366, 399, 405, 434, 491, 496, 542, 610, 674, 684, 913, 969}

33

Returns: 4
{1, 23, 29, 52, 224, 274, 343, 351, 400, 404, 412, 494, 502, 565, 582, 737, 826, 897}

693100438601

Returns: 52542731129
{1, 28, 39, 164, 209, 214, 448, 452, 488, 519, 541, 580, 588, 684, 691, 764, 860, 901, 1000}

89868

Returns: 4856
{1, 59, 99, 163, 165, 199, 360, 393, 464, 473, 497, 517, 561, 601, 632, 635, 674, 727, 967, 998}

5711816123

Returns: 137358325
{1, 11, 41, 66, 134, 195, 283, 401, 412, 414, 526, 536, 578, 603, 679, 692, 752, 815, 828, 846}

2

Returns: 1
{1, 19, 22, 39, 133, 147, 159, 249, 347, 498, 570, 615, 644, 646, 657, 680, 685, 694, 709, 722, 731, 797}

132216

Returns: 12937
{1, 68, 132, 157, 264, 296, 363, 377, 407, 435, 442, 460, 537, 642, 707, 732, 762, 802, 813, 866, 873, 910, 962}

9466214218989

Returns: 206642929935
{1, 84, 93, 229, 256, 291, 301, 304, 321, 390, 443, 535, 575, 611, 699, 756, 779, 794, 883, 897, 923, 965, 992}

10

Returns: 1
{1, 68, 71, 106, 132, 149, 159, 235, 249, 273, 421, 435, 487, 503, 548, 626, 689, 712, 745, 770, 781, 792, 807, 853, 866}

691781893470

Returns: 20769433294
{1, 29, 58, 106, 133, 182, 206, 316, 369, 421, 475, 500, 599, 638, 673, 687, 694, 699, 794, 835, 850, 887, 919, 953, 963, 983}

7633

Returns: 421
{1, 149, 203, 205, 296, 370, 384, 392, 483, 498, 514, 529, 557, 588, 598, 625, 638, 683, 696, 763, 777, 780, 806, 897, 922, 976}

2003584172

Returns: 30792788
{1, 4, 77, 96, 127, 175, 236, 241, 391, 421, 456, 463, 529, 619, 620, 630, 708, 734, 760, 804, 815, 830, 952, 953, 959, 976}

39135231341

Returns: 10385271433
{1, 14, 38, 58, 69, 74, 173, 239, 247, 254, 280, 381, 389, 435, 446, 474, 494, 552, 574, 580, 589, 660, 702, 837, 847, 854, 867, 871, 944}

75318

Returns: 7020
{1, 17, 23, 85, 113, 160, 216, 226, 252, 298, 383, 415, 470, 476, 482, 545, 563, 565, 569, 604, 612, 744, 753, 773, 897, 951, 985}

179625084847

Returns: 15135920860
{1, 9, 29, 79, 126, 198, 206, 309, 321, 323, 333, 347, 380, 392, 393, 436, 452, 488, 530, 570, 585, 598, 626, 666, 701, 726, 777, 819, 887, 996}

61026377943747

Returns: 9006905178444
{1, 16, 30, 62, 77, 83, 85, 102, 117, 183, 207, 229, 251, 388, 399, 449, 594, 648, 649, 672, 687, 689, 690, 698, 716, 728, 730, 755, 785, 830, 890, 919}

522787

Returns: 47785
{1, 2, 143, 206, 235, 243, 257, 259, 282, 386, 480, 501, 502, 512, 607, 620, 628, 682, 683, 748, 755, 772, 785, 797, 873, 884, 934, 941, 951, 955, 982, 984}

337192936

Returns: 173393930
{1, 99, 102, 165, 199, 244, 254, 271, 296, 313, 328, 356, 396, 415, 431, 436, 441, 445, 486, 502, 510, 513, 543, 562, 563, 569, 625, 674, 760, 761, 893, 937, 944}

8113978

Returns: 197693
{1, 3, 63, 99, 129, 130, 140, 153, 168, 191, 196, 211, 218, 233, 234, 342, 408, 498, 508, 515, 562, 576, 594, 641, 650, 708, 779, 786, 800, 816, 836, 928, 932, 937, 951}

6895334

Returns: 2508716
{1, 47, 60, 115, 139, 238, 241, 291, 345, 348, 378, 468, 507, 508, 513, 523, 565, 591, 599, 636, 644, 650, 651, 661, 710, 720, 748, 756, 778, 794, 853, 884, 893, 936, 957, 962}

10036

Returns: 422
{1, 32, 78, 82, 111, 123, 191, 204, 211, 244, 279, 286, 319, 376, 453, 454, 485, 524, 550, 561, 598, 681, 685, 717, 725, 733, 773, 811, 875, 901, 919, 925, 926, 932, 972, 980}

42

Returns: 2
{1, 9, 19, 42, 110, 113, 127, 135, 255, 311, 326, 328, 370, 374, 388, 404, 417, 489, 567, 570, 642, 683, 708, 715, 717, 750, 757, 760, 779, 832, 891, 892, 897, 931, 962, 986, 992}

4

Returns: 1
{1, 60, 74, 83, 106, 137, 186, 199, 260, 270, 291, 342, 345, 346, 393, 398, 411, 471, 518, 521, 535, 538, 568, 574, 618, 632, 676, 710, 745, 782, 792, 814, 819, 852, 910, 914, 955, 957}

864956482

Returns: 34345179
{1, 57, 93, 107, 189, 193, 210, 213, 218, 219, 225, 246, 278, 289, 314, 320, 322, 333, 356, 398, 410, 427, 465, 559, 598, 616, 624, 658, 674, 702, 725, 752, 756, 801, 820, 825, 854, 871, 894, 920}

991422285

Returns: 33406620
{1, 7, 20, 26, 45, 54, 78, 104, 108, 156, 181, 185, 206, 242, 248, 317, 320, 323, 344, 351, 452, 454, 461, 471, 475, 484, 500, 568, 582, 591, 683, 692, 712, 715, 756, 785, 869, 907, 941, 968, 990}

9022456918

Returns: 1594878748
{1, 54, 57, 60, 103, 122, 140, 192, 230, 232, 257, 271, 294, 338, 341, 346, 354, 371, 372, 425, 432, 434, 498, 560, 573, 591, 606, 619, 673, 687, 766, 808, 828, 831, 835, 883, 901, 909, 921, 925, 933}

66649034

Returns: 3143149
{1, 3, 17, 18, 50, 90, 167, 208, 250, 368, 376, 391, 410, 413, 418, 434, 495, 497, 500, 504, 536, 555, 558, 593, 646, 673, 689, 695, 701, 748, 775, 831, 833, 852, 859, 889, 906, 917, 934, 953, 954, 955, 994}

44650351

Returns: 17563673
{1, 37, 78, 94, 123, 147, 156, 179, 197, 213, 218, 226, 259, 318, 344, 355, 394, 395, 415, 416, 468, 489, 517, 522, 523, 552, 555, 580, 599, 621, 622, 625, 627, 662, 677, 686, 696, 761, 800, 831, 845, 868, 924, 988}

1381

Returns: 65
{1, 39, 43, 87, 184, 228, 292, 304, 329, 356, 357, 404, 412, 415, 448, 488, 493, 497, 530, 539, 590, 604, 616, 632, 642, 662, 665, 672, 681, 690, 703, 707, 750, 752, 761, 802, 817, 824, 825, 846, 854, 865, 898, 918}

59221

Returns: 3411
{1, 19, 54, 65, 69, 75, 84, 93, 108, 134, 242, 278, 282, 301, 373, 427, 443, 447, 448, 452, 459, 475, 533, 559, 573, 580, 587, 601, 638, 654, 655, 662, 761, 782, 786, 818, 819, 821, 838, 848, 856, 972, 982, 984, 990}

222565580314

Returns: 16636215096
{1, 53, 66, 72, 77, 98, 115, 128, 136, 147, 153, 165, 184, 218, 243, 272, 275, 287, 292, 300, 374, 386, 387, 408, 410, 416, 476, 523, 558, 601, 610, 639, 651, 709, 714, 731, 784, 823, 835, 839, 857, 895, 901, 938, 990}

72133877

Returns: 3205941
{1, 13, 22, 36, 54, 111, 151, 152, 200, 205, 211, 217, 225, 227, 229, 246, 275, 334, 362, 374, 431, 439, 479, 494, 510, 515, 530, 550, 573, 596, 611, 626, 679, 685, 727, 767, 831, 847, 859, 861, 869, 881, 889, 895, 907, 931, 995}

500

Returns: 55
{1, 83, 100, 104, 105, 122, 124, 164, 184, 218, 232, 241, 266, 276, 280, 370, 384, 390, 399, 442, 465, 520, 541, 597, 627, 631, 642, 656, 680, 712, 719, 733, 742, 759, 762, 763, 797, 809, 846, 854, 879, 898, 900, 911, 958, 965, 973, 986, 993}

763856971

Returns: 30000414
{1, 13, 18, 69, 83, 115, 116, 137, 141, 167, 168, 177, 193, 203, 244, 254, 278, 310, 341, 349, 375, 428, 430, 433, 435, 437, 448, 459, 462, 489, 504, 511, 544, 550, 567, 596, 602, 615, 634, 653, 669, 701, 723, 726, 751, 770, 881, 905, 944, 996}

4959203061579

Returns: 642306420626
{1, 962}

103638

Returns: 108
{1, 818, 848, 910}

3613395797601

Returns: 11912293821
{1, 818, 873, 891, 906, 987}

38044

Returns: 188
{1, 826, 840, 879, 898, 933, 963, 967}

160160

Returns: 1144
{1, 803, 817, 827, 841, 843, 848, 908, 939, 953}

4468552

Returns: 42165
{1, 801, 872, 873, 875, 877, 884, 886, 928, 941, 960}

93631137010

Returns: 975324315
{1, 832, 836, 837, 846, 868, 875, 887, 911, 925, 930, 970, 999}

234889708

Returns: 2821490
{1, 819, 822, 824, 827, 843, 877, 887, 914, 926, 932, 935, 941, 952, 967}

115372422015

Returns: 1670334908
{1, 806, 842, 850, 856, 880, 888, 897, 899, 917, 921, 929, 947, 968, 985, 993, 995}

1282

Returns: 17
{1, 821, 823, 824, 830, 836, 839, 841, 856, 885, 892, 915, 939, 945, 957, 975, 979, 994}

114048690362432

Returns: 1950530921673
{1, 803, 817, 818, 832, 834, 836, 841, 848, 852, 905, 906, 926, 946, 948, 951, 968, 982, 983, 985, 999}

797807166124822

Returns: 15972115437912
{1, 800, 802, 812, 824, 836, 841, 845, 848, 852, 868, 870, 911, 918, 921, 932, 944, 945, 967, 977, 980, 988, 990, 998}

8477847999

Returns: 195381239
{1, 801, 803, 805, 807, 837, 848, 866, 877, 879, 904, 905, 910, 915, 936, 938, 946, 957, 979, 981, 984, 989, 999}

52566

Returns: 1125
{1, 811, 825, 838, 862, 869, 876, 878, 879, 886, 888, 890, 918, 921, 928, 939, 945, 952, 953, 954, 962, 963, 979, 980, 982, 998}

2946

Returns: 73
{1, 806, 808, 824, 833, 837, 840, 845, 846, 863, 874, 875, 876, 887, 902, 909, 913, 925, 932, 938, 939, 949, 950, 954, 956, 957, 976, 978, 989, 995}

7556829

Returns: 220228
{1, 800, 808, 810, 828, 829, 834, 835, 860, 861, 863, 865, 867, 871, 875, 880, 889, 891, 897, 901, 910, 911, 916, 939, 959, 962, 967, 971, 994, 996, 999}

34933586667784

Returns: 1049056656575
{1, 804, 807, 817, 825, 830, 837, 856, 863, 864, 866, 870, 874, 884, 891, 892, 893, 895, 900, 903, 905, 908, 916, 919, 922, 933, 936, 950, 975, 980, 989, 994, 997}

24019

Returns: 653
{1, 800, 801, 805, 808, 811, 820, 831, 837, 841, 842, 856, 860, 865, 870, 888, 889, 898, 903, 916, 917, 922, 924, 933, 934, 944, 946, 958, 961, 976, 978, 990, 996, 999}

645072563

Returns: 21308616
{1, 800, 802, 813, 815, 817, 826, 828, 839, 841, 847, 849, 853, 861, 863, 866, 881, 887, 897, 898, 900, 902, 906, 916, 926, 934, 938, 949, 950, 964, 965, 985, 991, 993}

979854

Returns: 32534
{1, 806, 807, 811, 813, 814, 822, 828, 829, 831, 832, 833, 843, 845, 856, 857, 861, 863, 864, 870, 875, 881, 887, 888, 896, 899, 906, 911, 928, 929, 933, 946, 953, 957, 961, 974, 977, 998}

1242079753696

Returns: 46049048913
{1, 809, 822, 823, 827, 836, 841, 842, 851, 859, 860, 866, 878, 883, 886, 889, 906, 908, 909, 912, 915, 918, 921, 923, 927, 934, 935, 944, 949, 955, 957, 958, 960, 963, 974, 976, 981, 986, 993}

6097832552

Returns: 233350978
{1, 800, 803, 812, 830, 832, 838, 845, 849, 855, 862, 864, 879, 882, 886, 889, 891, 894, 920, 922, 923, 928, 935, 936, 939, 945, 949, 950, 953, 954, 960, 968, 973, 974, 990, 998, 999}

69634567748

Returns: 2509353657
{1, 802, 803, 810, 824, 829, 836, 855, 856, 859, 861, 863, 866, 873, 875, 877, 889, 892, 895, 898, 899, 903, 904, 906, 910, 911, 915, 919, 920, 922, 923, 924, 930, 934, 937, 939, 943, 963, 973, 989, 990, 994}

681154578679157

Returns: 28095913205009
{1, 801, 806, 807, 809, 812, 814, 821, 836, 842, 846, 855, 862, 865, 868, 870, 876, 880, 889, 890, 892, 897, 910, 920, 922, 926, 927, 929, 932, 933, 934, 936, 937, 941, 942, 946, 957, 959, 966, 968, 978, 985, 993, 994, 995, 999}

30956453

Returns: 1394336
{1, 21, 367, 563, 731, 987}

6248

Returns: 312
{1, 23, 29, 52, 274, 343, 351, 400, 494, 502, 582, 826, 897}

826

Returns: 62
{1, 14, 75, 83, 96, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 128, 129, 130, 141, 142, 173, 194, 213, 317, 402, 542, 712 }

1234567891234

Returns: 199403521765
{1, 14, 75, 83, 96, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 128, 129, 130, 141, 142, 173, 194, 213, 317, 402, 542, 712 }

12345678912345

Returns: 1994035217580
{1, 2, 5, 8, 9, 13, 17, 29, 33, 37, 39, 40, 45, 67, 101, 254, 331, 378, 399, 420, 499, 501, 502, 503, 504, 645, 667, 889, 998, 1000 }

54389543543254

Returns: 39704366786575
{1, 998, 1000 }

498002

Returns: 500
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 17, 18, 20, 100, 201, 303, 401, 499, 599, 600, 700, 800, 900, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000 }

999999999999999

Returns: 965000000000000
{1, 999, 1000 }

997002

Returns: 999
{1, 2 }

1000000000000000

Returns: 500000000000001
{1, 30, 60 }

1000000000000000

Returns: 50000000000000
{1, 991, 992, 994, 995, 997, 998 }

1000000000000000

Returns: 6012024047413
{1, 302, 402, 595, 596, 597, 598, 599, 600, 601, 602 }

6026026021206

Returns: 100100100013
{1, 999, 1000 }

56943

Returns: 58
{1, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948 }

999999999999999

Returns: 51687763712276
{1, 8, 9, 10 }

17

Returns: 4
{1, 999, 1000 }

998002

Returns: 1001
{1, 999, 1000 }

776223

Returns: 778
{1, 2, 3, 4, 5, 6, 7, 8, 9, 997, 998, 999, 1000 }

900000007000013

Returns: 801000006229904
{1, 999, 1000 }

501498

Returns: 503
{1, 999, 1000 }

100000007

Returns: 199010
{1, 4, 8, 16, 30 }

32

Returns: 15
{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 83, 87, 103, 107, 113, 117 }

987987987987987

Returns: 819101152434485
{1, 999, 1000 }

68931

Returns: 70

Statistics

Problem Statement for "ChangeOMatic"

Problem Statement

Definition

Notes

Constraints

Examples