Statistics

Problem Statement for "TeleportAndLoader"

Problem Statement

The year 2100. Your company is located in a huge skyscraper. The company purchased new equipment that has been dropped off at the entrance to your building at level 0. It is a number of boxes. Each box has been assigned to a floor in the building (several boxes may be assigned to one floor). You have to deliver the boxes to their respective floors. To facilitate this, you may use a teleporter. A teleporter can move any number of boxes to any floor for a fixed price, regardless of the number of items or their destination. To help you move the boxes, you can use loaders along with teleporters. Loaders can move boxes from any level to any other level (up or down), but the cost is proportional to the number of boxes moved and the difference between the current and destination levels (so, moving 2 boxes from level 10 to level 20 will cost you the same price as moving one box from level 10 to level 30, and half as much as moving 2 boxes from level 30 to level 50).
You will be given a int[] boxes, an int teleport_cost and an int loader_cost. The ith element of boxes gives you the level to which the ith box must be delivered. teleport_cost gives you the cost of one teleportation, and loader_cost gives you the cost for moving one box one level up or down using a loader. You must return the cheapest cost for delivering all the boxes.
For example: boxes = {1000, 40, 50, 10}
teleport_cost = 200
loader_cost = 10
One optimal way (there are many) to deliver these boxes is:
1. Teleport box number 0 to level 1000 - 200 units.
2. Teleport boxes 1 and 2 to level 40 - 200 units.
3. Move box number 2 from level 40 to level 50 - 10*10 = 100 units.
4. Move box number 3 from level 0 to level 10 - 10*10 = 100 units.
The total cost is 600 units, so your method should return 600.

Definition

Class:
TeleportAndLoader
Method:
cheapTransportation
Parameters:
int[], int, int
Returns:
int
Method signature:
int cheapTransportation(int[] boxes, int teleport_cost, int loader_cost)
(be sure your method is public)

Constraints

  • boxes will contain between 1 and 50 elements, inclusive.
  • Each element of boxes will be between 1 and 1000000 (106), inclusive.
  • loader_cost and teleport_cost will be between 1 and 1000000 (106), inclusive.

Examples

  1. {1, 2, 3, 4, 5}

    10000

    1

    Returns: 15

    Teleporting is too expensive. Use a loader.

  2. {1000, 40, 50, 10}

    200

    10

    Returns: 600

    The example from the problem statement.

  3. {1, 10, 254, 987, 1000000}

    1

    1000

    Returns: 5

    A loader is too expensive. Use a teleport.

  4. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    24

    1

    Returns: 48

  5. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000, 1000}

    24000

    1000

    Returns: 71000

  6. {577198, 828600}

    491359

    917843

    Returns: 982718

  7. {178880, 727526, 311016, 93374, 150170, 456122, 4010, 386545, 584617, 621171, 678462, 360059, 622803, 821533, 309897, 744979, 947553, 145474, 240883, 214799, 863627, 401273, 304861, 24385, 94694, 57010, 940283, 279603, 707858, 743497, 210762, 479469, 971763, 110614, 394753, 623587, 370156, 230436}

    822530

    769354

    Returns: 31256140

  8. {673504, 65717, 516152, 972145, 926710, 310437, 72990, 699157, 898842, 596196}

    182837

    486160

    Returns: 1828370

  9. {749416, 286583, 698774, 739487, 125377, 854036, 529679, 436108, 972944, 562355, 483384, 867325, 467279, 304757, 580201, 779860, 407513, 911029, 586052, 544199, 863642, 673203, 862127, 112761, 321964, 292345}

    143751

    854725

    Returns: 3737526

  10. {765259, 147002, 62826, 873216, 118567, 14117, 465771, 702557, 75448, 206713, 297448, 238592, 545644, 164517, 986713, 946195, 344183, 468100, 640097, 448954, 49917, 296233, 787421, 206644, 618463, 477613, 649876, 848640, 738580, 384189, 755569}

    926249

    193620

    Returns: 28713719

  11. {598360, 506083, 758627, 635708, 823153, 589889, 933630, 745045, 684000, 322583, 313179, 111890, 871763, 158335, 81079, 656840, 558460, 418306, 476514, 156331, 755322, 846983, 894743, 307967, 130068, 803538, 624980, 74897, 669330, 107518, 232298, 942565, 678118, 504389, 508813, 521392}

    704545

    620405

    Returns: 25363620

  12. {724104, 638884}

    503766

    508390

    Returns: 1007532

  13. {566366, 978646, 180384, 134762, 974627, 28338, 57655, 134868, 885612, 738875, 15130, 724632, 222068, 172640, 349328, 376677, 821827, 539626, 817923, 148646, 412260, 139876, 67439, 587310, 561231, 318114, 827138, 291808, 916809, 761630, 369878, 233885, 234256, 555056, 83538, 437097, 265913, 238151, 128954, 82049}

    60345

    936409

    Returns: 2413800

  14. {968858, 547863, 710408, 265005, 538978, 408247, 599262, 700968, 445912, 7964, 615806, 590146, 227393, 4428, 84676, 875067, 830678, 708822, 542703, 146707, 745797, 31890, 659724}

    87566

    970061

    Returns: 2014018

  15. {148635, 299945, 376712, 223160, 246534, 923109, 924453, 82801, 175998, 794892, 215468, 3769, 116415, 318040, 258194}

    253158

    635907

    Returns: 3797370

  16. {200799, 661673, 930467, 943681, 154652, 583433, 965554, 592550, 261407, 358038, 814202, 71399, 604073, 202160, 659466, 618715, 451701, 406856, 606205, 972898, 401190, 917589, 452643, 725051, 292267, 417917, 727746, 917404, 406926, 316398, 584363, 751764, 754758, 142205, 279697, 932377, 530113, 929208, 530671, 449705, 92082, 77029, 363315, 714147, 404070, 691743, 203711, 630671}

    557101

    558051

    Returns: 26740848

  17. {475994, 745544, 696710, 381398, 51830, 173063, 318804, 217330, 496010, 450521, 620777, 410359, 862965, 638055, 576885, 396314, 291028, 627401, 19032, 466879, 959412, 744627, 827897, 596610, 80813, 473605, 603583, 835689, 351011, 273350, 237790, 380891, 119743, 644916, 187549, 923799, 988203, 923817, 976870, 911644, 189632, 271257, 749808, 175732, 492084, 825876, 127315, 587485, 780197}

    745016

    663709

    Returns: 36505784

  18. {73282, 692860, 570381, 798239, 653238, 209995, 288024, 787156, 48010, 356660}

    351425

    426093

    Returns: 3514250

  19. {716347, 673898, 548584, 55477, 266438, 884499, 89580, 726798, 884871, 300886, 660765, 848784, 892931, 934535, 450111, 362843, 437174, 674, 792066, 91395, 700827, 157147, 49355, 19664, 54937, 652443, 21249, 401670}

    800024

    845142

    Returns: 22400672

  20. {563475, 219308, 800351, 492623, 104774, 154468, 728795, 657637, 968705, 296581, 297562, 729253, 559505, 974686, 783639, 456818, 763210, 644932, 605941, 517502, 460911, 962188, 258208, 748964, 640043, 656036, 569558, 457063, 130616, 51177, 676341, 323670, 420438}

    226695

    170510

    Returns: 7480935

  21. {821446, 4348, 384132, 847751, 912659, 666527, 751755, 980478, 371115, 926841, 465112, 890780, 40427, 958070, 168217, 119606, 121634, 594707, 749938, 685306, 828388, 791210, 174398, 185595, 200984, 194391}

    311124

    202048

    Returns: 8089224

  22. {779903, 1460, 436821, 472507, 767245, 572095, 944916, 877062, 502648, 765775, 261932, 810205, 566053, 534810, 721025, 749567, 936897, 816313, 404494, 53668, 788, 774226, 158059, 686034, 354715, 817447, 650303, 488896, 81104, 146147, 940317, 382834, 47834, 245920, 262276, 213235, 866896, 908866, 623042}

    177189

    364461

    Returns: 6910371

  23. {915638, 559934, 535749, 992889, 860151, 383292, 175998, 759734, 31661, 832754, 837128}

    736385

    665938

    Returns: 8100235

  24. {32793, 459008, 234429, 160942, 513249, 772929, 218033, 789234, 569826, 872340, 551891, 662234, 832380, 375036, 574408, 122333, 920207, 962129, 869916, 456228, 649574, 639434, 16885, 142274, 298699, 574982, 621808, 432839, 757140, 528021, 7767, 341924, 473787, 51647, 24699, 992513, 723273, 842663, 611270, 864472, 766361, 14488, 641414, 392029, 295612}

    905443

    953393

    Returns: 40744935

  25. {577198, 828600}

    491359

    918

    Returns: 982718

  26. {764179, 879728, 525312, 15094, 373151, 169457, 121005, 9387, 544585, 616622, 170679, 461361, 58623, 802822, 532310, 896745, 978948, 552146, 473241, 882215, 798864, 626402, 272305, 860025, 384095, 693058, 9941, 282280, 602708, 857744, 496211, 761480, 468972, 762111, 613395, 752624, 586371, 155231, 435823, 529770, 353174, 673504}

    65717

    517

    Returns: 2760114

  27. {972145, 926710, 310437, 72990, 699157, 898842, 596196, 182837, 486160}

    516750

    416

    Returns: 4650750

  28. {582699, 773740, 486126, 376855, 35530, 678437, 107973, 943563, 354484, 383868, 324468, 278305, 756581, 200780, 859408}

    512912

    29

    Returns: 7368844

  29. {586052, 544199, 863642, 673203, 862127, 112761, 321964, 292345, 143751, 854725, 614766, 258148, 1063, 825874, 215119, 566015, 116466, 770703, 556076, 447207, 712298, 447239, 591546, 643165, 516987, 712947, 194345, 182469, 99641, 96449, 953050, 916297, 232788, 420207, 643619, 462478, 612650, 875849, 639739, 579385, 188756, 568927, 248194, 619716, 598360, 506083, 758627, 635708, 823153, 589889}

    933630

    746

    Returns: 44586688

  30. {684000, 322583, 313179, 111890}

    871763

    159

    Returns: 3487052

  31. {81079, 656840, 558460, 418306, 476514, 156331, 755322, 846983, 894743, 307967, 130068, 803538, 624980, 74897, 669330, 107518, 232298, 942565}

    678118

    505

    Returns: 12206124

  32. {508813, 521392, 704545, 620405, 6725, 103639, 883504, 765509, 389805, 566366, 978646, 180384, 134762, 974627, 28338, 57655, 134868, 885612, 738875, 15130}

    724632

    223

    Returns: 13537098

  33. {172640, 349328, 376677, 821827, 539626}

    817923

    149

    Returns: 4089615

  34. {412260, 139876, 67439, 587310, 561231, 318114, 827138, 291808, 916809, 761630, 369878, 233885, 234256, 555056, 83538, 437097, 265913, 238151, 128954, 82049, 60345, 936409, 443969, 857548, 862711, 407266, 4539, 977409, 246600, 261701, 967446, 911008}

    963616

    806

    Returns: 30171122

  35. {145228, 392005, 427085, 675876, 66831, 677709, 821543, 702147, 706746, 796032, 889660, 723088, 565971, 60282, 148635, 299945, 376712, 223160, 246534, 923109, 924453, 82801, 175998, 794892, 215468, 3769, 116415, 318040, 258194, 253158}

    635907

    962

    Returns: 19077210

  36. {798662, 672931, 466944, 680155, 651584, 432966, 553593, 549262, 406359, 37815, 201072}

    398605

    73

    Returns: 4302213

  37. {159660, 465619, 714452, 700407, 855607, 204973, 897402, 189918, 588453, 642726, 50293}

    266418

    917

    Returns: 2930598

  38. {745918, 403407, 925317, 397585, 362752, 763755, 757143, 204280, 696933, 376531, 112930, 207531, 670450, 704093, 81078, 28364, 314715, 146405, 69692, 742204, 710631, 670558, 100559, 50998, 475994, 745544, 696710, 381398, 51830, 173063, 318804, 217330, 496010, 450521, 620777, 410359}

    862965

    639

    Returns: 28597023

  39. {54577, 884397, 313292, 27628, 400020, 31467, 878960, 411745, 626828, 896597, 609081, 812474, 604604, 582836, 688352, 10274, 349238, 789381, 890120, 742645, 915188, 548924, 798989, 202924, 816977, 869912, 643190, 631272, 256750, 807176, 731493, 83826, 875128, 314588, 484781, 196746, 15664, 708179, 73282, 692860, 570381, 798239, 653238, 209995, 288024, 787156, 48010, 356660, 351425, 426093}

    558717

    347

    Returns: 27528378

  40. {65536}

    65536

    65536

    Returns: 65536

  41. { 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 1000000 }

    1000000

    1000000

    Returns: 19000000

  42. { 65537 }

    1000000

    65536

    Returns: 1000000

  43. { 1, 10, 254, 987, 1000000 }

    1000000

    1000000

    Returns: 5000000

  44. { 999, 1001, 1001, 1001 }

    100

    10

    Returns: 120

  45. { 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 1000000 }

    1000000

    500

    Returns: 10000000

  46. { 3000 }

    1000000

    1000000

    Returns: 1000000

  47. { 10000, 30000, 50000, 70000, 90000, 110000, 130000, 150000, 170000, 190000, 210000, 230000, 250000, 270000, 290000, 310000, 330000, 350000, 370000, 390000, 410000, 430000, 450000, 470000, 490000, 510000, 530000, 550000, 570000, 590000, 610000, 630000, 650000, 670000, 690000, 710000, 730000, 750000, 770000, 790000, 810000, 830000, 850000, 870000, 890000, 910000, 930000, 950000, 970000, 990000 }

    10000

    1

    Returns: 500000

  48. { 83, 91, 57, 100, 1, 1000, 742, 677, 709, 150, 150, 150, 150, 223, 221, 234, 999, 998, 997, 996, 567, 294, 12, 13, 445, 446, 449, 487, 322, 981, 116, 56784, 56789, 68020, 61475, 61562, 5000, 9999, 9998, 10005, 1000000, 8884 }

    5000

    8

    Returns: 64136

  49. { 1000000 }

    10000

    4000

    Returns: 10000

  50. { 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, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }

    10

    1

    Returns: 158

  51. { 100, 110, 120, 120, 110, 100, 100, 120 }

    30

    1

    Returns: 80

  52. { 1, 2, 3, 10, 11, 12, 19, 20, 21, 22, 23, 49, 50, 51, 52, 53, 54, 55, 99, 100, 101, 102, 110, 10000 }

    200

    10

    Returns: 1390

  53. {999, 1001, 1001, 1001}

    100

    10

    Returns: 120

  54. { 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 1000000 }

    1000000

    1000000

    Returns: 19000000

  55. { 65537 }

    1000000

    65536

    Returns: 1000000

  56. { 1, 10, 254, 987, 1000000 }

    1000000

    1000000

    Returns: 5000000

  57. { 999, 1001, 1001, 1001 }

    100

    10

    Returns: 120

  58. { 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 1000000 }

    1000000

    500

    Returns: 10000000

  59. { 3000 }

    1000000

    1000000

    Returns: 1000000

  60. { 10000, 30000, 50000, 70000, 90000, 110000, 130000, 150000, 170000, 190000, 210000, 230000, 250000, 270000, 290000, 310000, 330000, 350000, 370000, 390000, 410000, 430000, 450000, 470000, 490000, 510000, 530000, 550000, 570000, 590000, 610000, 630000, 650000, 670000, 690000, 710000, 730000, 750000, 770000, 790000, 810000, 830000, 850000, 870000, 890000, 910000, 930000, 950000, 970000, 990000 }

    10000

    1

    Returns: 500000

  61. { 83, 91, 57, 100, 1, 1000, 742, 677, 709, 150, 150, 150, 150, 223, 221, 234, 999, 998, 997, 996, 567, 294, 12, 13, 445, 446, 449, 487, 322, 981, 116, 56784, 56789, 68020, 61475, 61562, 5000, 9999, 9998, 10005, 1000000, 8884 }

    5000

    8

    Returns: 64136

  62. { 1000000 }

    10000

    4000

    Returns: 10000

  63. { 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, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }

    10

    1

    Returns: 158

  64. { 100, 110, 120, 120, 110, 100, 100, 120 }

    30

    1

    Returns: 80

  65. { 1, 2, 3, 10, 11, 12, 19, 20, 21, 22, 23, 49, 50, 51, 52, 53, 54, 55, 99, 100, 101, 102, 110, 10000 }

    200

    10

    Returns: 1390

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: