Statistics

Problem Statement for "GetGas"

Problem Statement

I have a car. Currently, there are G gallons of gas in the car. The car will always do 25 miles per gallon of gas.

I need to take a trip to another city. During the trip I want to stop at exactly one gas station to take a break and fill up if necessary.

There are N gas stations that are around the route of the trip. We will number them 0 to N-1. You are given the information about them: for each i, the distance from my home to gas station number i is Dto[i] miles, the distance from that gas station to the destination is Dfrom[i] miles, and the price of gas at this station is gasPrice[i] cents per gallon.

Some notes:

  • The gas tank in my car is large enough: regardless of how much gas you want to buy, you may assume that there's enough room for it.
  • When filling up, I will only purchase as much gas as I need in order to reach my destination.
  • I have to stop at exactly one of the N given gas stations. If I have enough (or more than enough) gas to reach my destination from there, I won't purchase any gas during the stop.
  • The gas stations are not necessarily located along the same road, so it's possible that the total length of the trip will be different for different gas stations.

Calculate and return the minimum total amount (in cents) I'll have to spend on gas during my trip.

Definition

Class:
GetGas
Method:
optimize
Parameters:
int, int[], int[], int[]
Returns:
double
Method signature:
double optimize(int G, int[] Dto, int[] Dfrom, int[] gasPrice)
(be sure your method is public)

Notes

  • The return value is not necessarily an integer: it may be optimal to purchase a fraction of a gallon of gas.
  • Your return value will be considered correct if it has an absolute or a relative error at most 10^(-9).
  • The constraints guarantee that there will always be some valid way to reach the destination.

Constraints

  • G will be between 1 and 100, inclusive.
  • Dto will have between 1 and 50 elements, inclusive.
  • Dfrom will have the same number of elements as Dto.
  • gasPrice will have the same number of elements as Dto.
  • Each element of Dto will be between 1 and 1000, inclusive.
  • Each element of Dfrom will be between 1 and 1000, inclusive.
  • Each element of gasPrice will be between 1 and 1000, inclusive.
  • min(Dto) will not exceed 25*G.

Examples

  1. 10

    {250, 250}

    {500, 600}

    {400, 400}

    Returns: 8000.0

    There are two gas stations. The amount of gas I have in my car is exactly enough to reach either of them with an empty tank. The price of gas is the same for both stations: $4.00 per gallon. Thus, clearly it makes sense to choose the station that's closer to my goal. We need 500 / 25 = 20 gallons of gas for the rest of the journey. At $4.00 we will pay $80, i.e., exactly 8000 cents.

  2. 10

    {250, 250}

    {500, 600}

    {500, 400}

    Returns: 9600.0

    Similar situation to Example 0, but now the gas at gas station #0 costs more and therefore the other gas station is the better choice: even though the journey is longer, the total amount paid for gas will be smaller.

  3. 100

    {10, 20, 30, 1000}

    {30, 20, 10, 1000}

    {423, 434, 445, 456}

    Returns: 0.0

    Regardless of where we stop, we won't have to purchase any extra gas, we have enough for the whole trip.

  4. 10

    {240, 260}

    {1000, 10}

    {417, 233}

    Returns: 16513.2

    We would love to stop at gas station #1: it's close to our goal and it has cheap gas. The problem is that we don't have enough gas to get there, so we are forced to choose station #0 instead.

  5. 1

    {25}

    {1}

    {1}

    Returns: 0.040000000000000036

  6. 1

    {25}

    {1000}

    {1000}

    Returns: 40000.0

  7. 39

    {10, 20, 30, 1000}

    {10, 20, 30, 1000}

    {423, 434, 445, 456}

    Returns: 0.0

  8. 5

    {142, 145, 130, 119, 136, 137, 92, 140, 90, 100, 87, 120, 148, 88, 127, 141, 116, 117, 132, 143, 117, 91, 134}

    {132, 130, 112, 117, 91, 103, 129, 99, 133, 136, 119, 99, 116, 129, 114, 147, 101, 140, 132, 123, 117, 120, 132}

    {546, 579, 42, 496, 320, 577, 799, 405, 267, 968, 748, 532, 819, 227, 621, 117, 643, 862, 213, 389, 498, 260, 986}

    Returns: 835.3599999999999

  9. 1

    {19, 25, 27, 29, 29, 18, 18, 21, 25, 30, 26, 25, 24, 29, 29, 23, 22, 29, 17, 26, 21, 27, 26, 25, 27, 24, 28, 27, 29}

    {22, 30, 17, 26, 20, 20, 22, 23, 30, 28, 19, 19, 24, 20, 19, 18, 19, 28, 29, 26, 22, 25, 23, 18, 21, 24, 17, 27, 18}

    {425, 69, 379, 22, 271, 43, 144, 186, 757, 524, 856, 503, 206, 802, 792, 832, 507, 541, 465, 578, 581, 11, 712, 76, 180, 856, 155, 944, 557}

    Returns: 22.36

  10. 3

    {67, 55, 76, 59, 53, 57, 71, 55, 87, 71, 67, 86, 61, 87, 89, 69, 88, 57, 88, 83, 73, 87, 55, 59, 78, 78, 74, 71, 88, 83, 90, 60, 56, 84, 59, 81, 81, 53, 79, 88, 85}

    {56, 70, 83, 84, 59, 67, 74, 73, 62, 81, 53, 89, 58, 81, 81, 69, 86, 53, 87, 64, 70, 54, 68, 86, 82, 76, 56, 58, 85, 89, 90, 82, 86, 75, 89, 71, 78, 65, 57, 58, 84}

    {829, 313, 415, 977, 341, 552, 857, 369, 872, 112, 836, 956, 96, 876, 638, 762, 437, 370, 52, 359, 597, 886, 58, 948, 402, 650, 827, 275, 261, 216, 297, 215, 477, 872, 678, 841, 838, 980, 307, 456, 958}

    Returns: 111.36

  11. 44

    {784, 809, 918, 892, 770, 777, 878, 991, 887, 903, 882, 927, 978, 990, 835, 845, 796, 847, 801, 813, 878}

    {856, 897, 879, 830, 898, 915, 901, 837, 850, 912, 775, 925, 942, 993, 867, 989, 922, 920, 948, 922, 946}

    {639, 940, 473, 632, 572, 184, 699, 719, 387, 835, 44, 186, 628, 952, 186, 639, 80, 497, 421, 62, 230}

    Returns: 980.32

  12. 39

    {885, 684, 753, 719, 968, 881, 682, 878, 937, 915, 873, 744}

    {943, 887, 734, 726, 897, 892, 963, 735, 998, 771, 937, 925}

    {450, 611, 849, 96, 405, 538, 518, 336, 443, 767, 936, 202}

    Returns: 1804.7999999999997

  13. 5

    {103, 149, 129, 100, 119, 149, 98, 132, 90, 137, 97, 115, 113, 119, 126, 101, 94, 123, 109, 149, 117, 138, 147, 87, 138, 117}

    {134, 100, 130, 95, 107, 100, 117, 110, 97, 105, 108, 108, 96, 98, 103, 137, 131, 102, 140, 124, 115, 131, 98, 127, 100, 91}

    {207, 831, 573, 139, 987, 339, 959, 996, 94, 854, 327, 788, 733, 680, 962, 968, 939, 440, 519, 560, 587, 771, 789, 697, 923, 361}

    Returns: 233.12000000000003

  14. 29

    {730, 853, 718, 758, 518, 606, 674, 532, 814, 726, 558, 731, 805, 570, 556, 678, 730, 537, 677, 602, 849, 716, 747, 772, 750, 861, 771, 568, 624, 608, 828, 520, 783, 759, 673, 579, 852, 590, 655, 544, 531}

    {816, 659, 529, 835, 823, 849, 510, 638, 683, 605, 791, 617, 696, 696, 575, 610, 736, 822, 524, 661, 815, 849, 660, 722, 563, 723, 721, 684, 761, 638, 530, 796, 859, 758, 624, 645, 714, 536, 519, 708, 604}

    {785, 428, 376, 533, 91, 354, 740, 992, 889, 640, 908, 643, 348, 452, 887, 857, 70, 903, 68, 998, 485, 274, 66, 167, 210, 233, 952, 433, 484, 813, 203, 304, 7, 117, 620, 578, 835, 13, 258, 547, 219}

    Returns: 208.51999999999998

  15. 14

    {330, 347, 254, 417, 410, 395, 351, 328, 382, 333, 246, 272, 250, 324, 257, 400, 300, 379, 401, 245, 253, 386, 395, 257, 343, 363, 293, 267, 315, 417, 407}

    {346, 375, 334, 254, 261, 322, 398, 324, 258, 401, 358, 363, 349, 330, 268, 309, 352, 340, 270, 341, 341, 290, 320, 252, 252, 392, 418, 392, 293, 277, 388}

    {229, 89, 8, 434, 438, 427, 725, 434, 593, 752, 131, 158, 792, 739, 758, 974, 760, 873, 385, 552, 657, 929, 472, 269, 656, 845, 657, 152, 77, 41, 605}

    Returns: 76.16

  16. 38

    {730, 701, 673, 735, 727, 930, 730, 978, 814, 956, 973, 879, 945, 914, 978, 962, 677, 750, 971, 942, 961, 989, 739, 783, 725, 742, 810, 980, 912, 998, 915, 900, 974, 823, 874, 895, 975, 758, 671, 884, 914, 915, 873, 840, 856, 949, 819}

    {822, 866, 857, 683, 984, 934, 802, 737, 904, 865, 716, 720, 968, 682, 853, 991, 839, 957, 740, 665, 798, 844, 746, 982, 685, 876, 911, 830, 740, 801, 796, 834, 874, 722, 770, 755, 983, 783, 809, 790, 900, 935, 839, 744, 935, 849, 722}

    {919, 150, 944, 182, 579, 948, 233, 553, 866, 586, 803, 541, 852, 795, 329, 655, 811, 655, 555, 211, 810, 653, 256, 972, 42, 375, 961, 390, 919, 773, 177, 502, 624, 956, 751, 923, 744, 175, 948, 895, 198, 413, 824, 746, 686, 55, 481}

    Returns: 772.8

  17. 35

    {650, 744, 660, 682, 954, 875, 994, 908, 954, 718, 752, 917, 811, 668, 742, 895, 795, 673, 804, 802, 944, 884, 727, 760, 740, 923, 958, 969, 945, 776, 903, 631, 1000, 928, 718, 763}

    {840, 778, 998, 670, 686, 915, 705, 745, 787, 752, 660, 762, 718, 631, 750, 925, 945, 723, 713, 961, 864, 865, 651, 807, 944, 623, 947, 915, 688, 666, 826, 766, 724, 823, 996, 709}

    {89, 220, 658, 650, 897, 681, 229, 562, 92, 569, 430, 317, 323, 383, 934, 122, 94, 709, 322, 466, 217, 788, 121, 669, 89, 549, 681, 349, 779, 581, 706, 496, 815, 225, 61, 327}

    Returns: 2047.16

  18. 48

    {937, 907, 991, 855, 859, 905, 957, 969, 896, 971, 970, 964, 912, 921, 951, 972, 903, 996, 924, 986, 893, 986, 885, 888, 901, 850, 847, 995, 970, 995, 906, 995, 915, 890, 927, 991, 994, 983, 926, 969, 884, 923, 935, 887, 880, 966, 859}

    {849, 940, 958, 955, 915, 999, 864, 966, 1000, 909, 925, 912, 895, 949, 859, 905, 996, 937, 922, 957, 914, 881, 901, 886, 932, 898, 919, 849, 895, 987, 961, 846, 931, 842, 912, 910, 981, 946, 975, 900, 956, 956, 853, 861, 873, 943, 953}

    {192, 254, 48, 412, 689, 464, 545, 537, 103, 572, 28, 558, 460, 554, 498, 862, 604, 166, 163, 807, 776, 973, 245, 283, 688, 327, 199, 571, 988, 692, 873, 505, 521, 821, 761, 282, 471, 262, 346, 538, 120, 983, 227, 780, 998, 261, 804}

    Returns: 778.3999999999999

  19. 9

    {188, 245, 251}

    {269, 248, 214}

    {754, 732, 891}

    Returns: 6997.120000000001

  20. 47

    {962, 987, 989, 877, 904, 982, 846, 888, 954, 862, 893, 914, 857, 864, 842, 869, 836, 952, 867, 976, 987}

    {964, 978, 979, 848, 895, 832, 904, 869, 844, 937, 892, 847, 898, 872, 973, 948, 981, 858, 856, 884, 959}

    {870, 247, 624, 320, 264, 690, 758, 920, 990, 466, 830, 27, 317, 938, 194, 764, 936, 27, 442, 179, 276}

    Returns: 632.8799999999999

  21. 46

    {513, 696, 832, 633, 712, 766, 598, 597, 598, 815, 532, 617, 668}

    {819, 713, 842, 660, 644, 827, 554, 662, 624, 529, 794, 748, 663}

    {242, 303, 854, 468, 184, 182, 568, 311, 811, 472, 297, 299, 627}

    Returns: 45.43999999999903

  22. 43

    {973, 769, 908}

    {905, 854, 897}

    {519, 436, 150}

    Returns: 4380.0

  23. 43

    {890, 809, 887, 895, 857, 929, 865, 890, 960, 978, 798, 816, 854, 834, 986, 837, 982, 783, 848, 863, 787, 774, 940, 863, 815}

    {812, 752, 817, 890, 961, 758, 957, 838, 853, 972, 888, 829, 934, 802, 816, 769, 925, 764, 814, 796, 908, 842, 840, 773, 927}

    {512, 268, 288, 788, 612, 377, 210, 833, 50, 845, 267, 499, 239, 681, 112, 541, 859, 313, 190, 407, 288, 759, 606, 936, 730}

    Returns: 1475.9999999999998

  24. 18

    {509, 356, 356, 396, 354, 386, 438, 340, 388, 492, 381, 353, 415, 487, 371, 371, 520, 507, 517, 360, 337, 389, 447, 352, 523, 434, 514, 390, 323, 342, 489, 457, 371, 368}

    {342, 365, 442, 413, 392, 498, 380, 318, 534, 400, 407, 422, 339, 337, 399, 381, 451, 528, 374, 463, 499, 491, 350, 377, 487, 520, 442, 456, 493, 476, 366, 512, 323, 504}

    {172, 25, 584, 891, 892, 322, 234, 703, 376, 865, 235, 251, 501, 380, 207, 845, 885, 435, 191, 475, 610, 630, 1000, 228, 37, 789, 417, 478, 955, 238, 434, 936, 785, 19}

    Returns: 271.0

  25. 33

    {610, 828, 676, 777, 673, 947, 578, 699, 829, 843, 583, 858, 728, 822, 737, 733, 889, 935, 917, 842, 940, 931, 958, 897, 835, 769, 896, 690, 922, 604, 688, 688, 967, 828, 878, 802, 832, 781, 855, 782}

    {648, 791, 759, 583, 933, 845, 750, 856, 957, 631, 968, 889, 762, 838, 774, 711, 655, 604, 687, 604, 865, 711, 929, 709, 667, 768, 891, 768, 695, 869, 873, 860, 645, 697, 631, 645, 761, 603, 651, 952}

    {945, 179, 400, 789, 859, 787, 711, 681, 278, 535, 65, 639, 750, 546, 998, 158, 963, 921, 247, 1000, 330, 466, 877, 531, 756, 727, 269, 97, 360, 782, 263, 10, 647, 567, 286, 547, 275, 477, 538, 629}

    Returns: 289.20000000000005

  26. 24

    {489, 526, 430, 470, 447, 616, 672, 525, 690, 714}

    {500, 608, 449, 705, 513, 701, 542, 666, 665, 638}

    {59, 720, 510, 711, 720, 893, 706, 794, 891, 240}

    Returns: 918.0400000000002

  27. 15

    {361, 378, 296, 425, 305, 305, 312, 347, 262, 413, 395, 450, 313, 402, 376, 303, 336, 395, 426, 373, 429, 382, 403, 373, 437, 267, 304, 411, 371, 364, 270, 404, 274}

    {277, 417, 438, 288, 315, 385, 310, 403, 270, 398, 292, 266, 346, 328, 384, 333, 287, 430, 291, 353, 385, 264, 333, 408, 379, 376, 309, 293, 328, 356, 381, 275, 387}

    {709, 34, 437, 657, 84, 706, 918, 779, 716, 216, 380, 201, 236, 742, 600, 147, 211, 508, 527, 763, 110, 298, 789, 621, 654, 757, 702, 554, 778, 882, 102, 813, 862}

    Returns: 823.2

  28. 3

    {61, 84, 68, 61, 69, 75, 61, 73, 86, 75, 60, 61, 79}

    {78, 88, 72, 63, 90, 76, 53, 58, 79, 62, 56, 58, 60}

    {106, 812, 79, 823, 881, 224, 30, 186, 842, 396, 99, 66, 834}

    Returns: 46.79999999999999

  29. 2

    {38, 40, 45, 56, 58, 39, 57, 39, 43, 42, 39, 36, 47, 40, 48, 60, 52, 35, 37, 42, 56, 57, 51, 48, 51, 55, 54, 37, 59, 46, 42, 46, 43, 41, 36, 44, 36, 40, 36, 51, 44, 44, 48, 57, 45, 36, 46, 58}

    {60, 55, 54, 43, 55, 40, 51, 60, 60, 55, 40, 41, 54, 35, 52, 59, 60, 49, 42, 60, 43, 48, 50, 35, 59, 55, 36, 45, 54, 48, 37, 37, 54, 45, 41, 43, 45, 57, 38, 54, 39, 54, 49, 47, 53, 45, 41, 43}

    {946, 281, 689, 469, 256, 494, 182, 589, 420, 398, 204, 37, 332, 977, 999, 46, 873, 241, 70, 120, 281, 246, 980, 494, 452, 774, 982, 144, 635, 99, 718, 9, 601, 342, 291, 986, 584, 42, 986, 272, 384, 833, 382, 374, 162, 932, 968, 91}

    Returns: 11.879999999999999

  30. 46

    {816, 801, 781, 883, 716, 851}

    {740, 625, 693, 603, 770, 758}

    {599, 693, 272, 256, 739, 247}

    Returns: 3440.6399999999994

  31. 49

    {935, 964, 983}

    {920, 911, 871}

    {711, 279, 815}

    Returns: 7254.0

  32. 4

    {72, 69, 60, 78, 59, 59, 66, 85, 63, 63, 90, 59, 77, 72, 69, 52, 84, 86, 69, 63, 84, 52, 84, 89, 71, 88, 71, 78, 88, 89, 75, 73, 67}

    {70, 65, 73, 77, 75, 65, 60, 74, 84, 53, 81, 61, 86, 74, 77, 57, 57, 56, 87, 78, 84, 61, 63, 62, 80, 56, 65, 75, 76, 64, 83, 56, 87}

    {509, 204, 58, 21, 331, 576, 200, 390, 13, 142, 570, 687, 403, 966, 377, 238, 112, 256, 205, 396, 264, 604, 473, 997, 832, 748, 801, 880, 990, 406, 432, 994, 496}

    Returns: 24.439999999999998

  33. 13

    {317, 379, 363, 316, 264, 239, 236, 259, 389, 274}

    {272, 239, 230, 318, 280, 232, 356, 261, 234, 314}

    {765, 260, 310, 425, 869, 832, 992, 761, 846, 147}

    Returns: 1546.4399999999998

  34. 29

    {589, 846, 588, 778, 725, 513, 572, 599, 758, 571, 720, 696, 519, 511, 804, 741, 611, 661, 592, 649, 771, 663, 843, 819, 719, 601, 671, 558, 806, 695, 790, 844, 621, 614, 822, 741, 734, 602, 622, 841, 647, 519, 830, 556, 709, 531, 693}

    {797, 831, 538, 731, 526, 561, 637, 681, 844, 615, 695, 512, 684, 620, 615, 607, 601, 679, 627, 705, 537, 847, 566, 573, 819, 767, 824, 721, 674, 693, 736, 755, 743, 760, 810, 593, 525, 720, 810, 766, 786, 744, 672, 696, 728, 594, 773}

    {665, 932, 568, 548, 235, 509, 422, 795, 765, 48, 360, 888, 312, 640, 253, 825, 481, 251, 823, 209, 95, 511, 974, 679, 387, 595, 223, 510, 25, 329, 255, 199, 339, 748, 601, 530, 850, 871, 230, 18, 405, 726, 872, 42, 523, 597, 343}

    Returns: 885.1199999999999

  35. 41

    {978, 952, 734, 811, 765, 822, 749, 845, 853, 912, 731, 767, 983, 977, 903, 930, 850, 897, 853, 791, 971, 997, 782}

    {992, 794, 875, 861, 740, 939, 903, 996, 915, 942, 999, 717, 849, 862, 962, 847, 914, 798, 817, 919, 926, 956, 746}

    {910, 301, 508, 99, 536, 966, 644, 820, 308, 729, 375, 851, 960, 530, 568, 252, 883, 88, 592, 72, 33, 132, 273}

    Returns: 1151.04

  36. 6

    {132, 177, 141, 130, 148, 117, 174, 132, 166, 128, 113, 168, 111, 130, 113, 151, 109, 161, 113, 176, 113, 166, 132, 125, 113, 126, 113}

    {129, 132, 128, 178, 132, 155, 175, 165, 156, 109, 174, 126, 129, 176, 111, 148, 116, 139, 169, 164, 161, 157, 133, 167, 131, 138, 170}

    {175, 675, 797, 838, 828, 397, 311, 591, 827, 639, 178, 739, 594, 918, 165, 316, 32, 44, 778, 552, 554, 660, 910, 727, 196, 203, 603}

    Returns: 96.0

  37. 28

    {775, 602, 773, 492, 752, 568, 615, 729, 713, 535, 753, 759, 516, 806, 798, 575, 829, 686, 637, 665, 643, 694, 744, 535, 642, 635, 648, 742, 796, 779, 551, 653, 757, 658, 665, 718, 592, 510, 802, 492, 502, 742}

    {750, 727, 829, 773, 637, 708, 661, 815, 556, 820, 525, 838, 542, 678, 598, 632, 738, 637, 797, 678, 651, 597, 586, 599, 585, 573, 596, 735, 680, 795, 645, 570, 694, 831, 653, 790, 686, 548, 550, 705, 493, 502}

    {205, 399, 175, 692, 721, 692, 692, 673, 495, 126, 40, 243, 678, 21, 215, 80, 864, 437, 422, 708, 889, 204, 227, 594, 843, 141, 485, 575, 461, 798, 80, 164, 913, 808, 318, 81, 680, 901, 443, 697, 598, 801}

    Returns: 1587.2000000000003

  38. 34

    {686, 668, 944, 706, 776, 860, 784, 725, 634, 666, 874, 936, 636, 722, 903, 751, 782, 829, 963}

    {918, 679, 925, 854, 821, 905, 818, 645, 677, 955, 977, 877, 615, 669, 838, 997, 899, 753, 908}

    {964, 697, 418, 474, 519, 420, 677, 535, 520, 425, 514, 933, 884, 940, 236, 520, 886, 276, 180}

    Returns: 8081.280000000001

  39. 8

    {155, 232, 238, 236, 180, 188, 164, 168, 191, 228, 240, 145, 159, 148, 238, 217, 163, 187, 185, 223, 195, 176, 231, 217, 147, 197, 195, 231, 142, 231, 232, 238, 210, 144, 142, 229, 146, 217, 155}

    {145, 153, 209, 154, 208, 171, 141, 209, 158, 178, 204, 201, 140, 150, 204, 216, 209, 219, 213, 173, 239, 200, 163, 167, 167, 182, 229, 238, 150, 225, 216, 214, 203, 154, 142, 199, 227, 196, 143}

    {44, 512, 471, 212, 768, 788, 121, 594, 411, 332, 435, 370, 817, 932, 755, 887, 797, 163, 893, 301, 425, 791, 688, 495, 583, 255, 304, 941, 466, 343, 828, 395, 541, 955, 320, 838, 445, 628, 773}

    Returns: 176.0

  40. 1

    {19, 28, 20, 26, 22, 20, 30, 18, 21, 29, 18, 29, 28, 24, 22, 18, 22, 17, 23, 20, 29, 25, 21, 25, 20, 19, 28, 29, 27}

    {17, 17, 21, 19, 26, 24, 29, 25, 21, 18, 24, 23, 20, 28, 23, 18, 22, 27, 23, 24, 29, 19, 21, 29, 21, 17, 26, 26, 27}

    {295, 249, 34, 904, 299, 349, 25, 503, 584, 394, 712, 945, 684, 284, 659, 431, 618, 181, 685, 114, 607, 6, 396, 979, 910, 665, 550, 784, 571}

    Returns: 4.5600000000000005

  41. 6

    {176, 130, 177, 161, 170, 174, 172, 124, 136, 150, 174, 166, 156, 152, 159, 141, 155, 126, 128, 131, 168, 150, 174, 137, 158, 150, 153, 138, 126, 155, 111, 110, 154, 173, 161, 146, 109, 140, 154, 154, 133, 154, 133, 152, 108, 120, 142}

    {120, 173, 119, 157, 155, 137, 152, 153, 151, 111, 148, 159, 126, 169, 125, 158, 108, 137, 138, 149, 112, 177, 167, 135, 117, 144, 176, 114, 159, 167, 175, 172, 153, 150, 170, 129, 178, 164, 131, 153, 166, 148, 136, 154, 140, 175, 155}

    {389, 102, 379, 3, 723, 8, 240, 282, 45, 828, 118, 459, 341, 476, 747, 245, 441, 820, 913, 873, 854, 854, 581, 8, 983, 990, 288, 455, 400, 334, 905, 161, 991, 961, 976, 372, 330, 863, 382, 847, 773, 960, 360, 240, 342, 915, 747}

    Returns: 39.040000000000006

  42. 3

    {64, 70, 87, 55, 90, 63, 77, 57, 69, 82, 59, 55, 55, 61, 70, 89, 62, 82, 85, 76, 84, 57, 67, 83, 72, 79, 85}

    {88, 66, 66, 70, 71, 59, 61, 83, 56, 64, 85, 77, 82, 85, 79, 65, 68, 68, 54, 76, 90, 76, 70, 85, 85, 62, 52}

    {424, 829, 321, 74, 185, 769, 260, 428, 875, 176, 157, 719, 132, 453, 195, 216, 793, 810, 916, 957, 574, 395, 443, 864, 276, 128, 905}

    Returns: 148.0

  43. 42

    {972, 990, 766, 749, 838, 737, 958, 744, 788, 949, 822, 961, 883, 969, 897, 946, 969, 962, 792}

    {985, 847, 868, 765, 736, 939, 764, 997, 749, 992, 784, 805, 753, 972, 860, 898, 974, 921, 964}

    {382, 71, 681, 771, 914, 901, 426, 455, 555, 277, 127, 719, 336, 12, 504, 584, 532, 544, 699}

    Returns: 427.68

  44. 30

    {581, 866, 621, 751, 560, 651, 627, 819, 850, 668, 615, 778, 878, 751, 635, 757, 685, 664, 837, 895, 788, 615, 881, 754, 713, 641, 553, 789, 529, 676, 618, 771, 619, 775, 673, 786}

    {603, 856, 898, 803, 859, 852, 878, 753, 877, 888, 713, 779, 846, 626, 571, 878, 860, 648, 737, 791, 579, 888, 648, 687, 861, 529, 549, 793, 783, 690, 576, 549, 831, 549, 756, 697}

    {541, 510, 747, 976, 378, 134, 858, 125, 245, 140, 53, 77, 241, 991, 259, 961, 634, 134, 136, 247, 117, 375, 332, 985, 406, 422, 617, 414, 413, 207, 250, 411, 424, 269, 715, 790}

    Returns: 1225.36

  45. 41

    {806, 966, 835, 806, 942, 729, 787, 727, 735, 743, 813, 877, 807, 900, 921, 891, 824, 774, 936, 893, 798, 762, 877, 911, 769, 976, 817}

    {770, 874, 997, 856, 992, 801, 893, 869, 854, 909, 719, 859, 723, 870, 925, 791, 857, 764, 885, 933, 947, 964, 988, 885, 782, 894, 768}

    {121, 187, 761, 713, 761, 350, 300, 966, 402, 651, 75, 997, 873, 753, 688, 636, 123, 613, 749, 32, 613, 488, 538, 490, 378, 559, 158}

    Returns: 1025.2800000000002

  46. 37

    {954, 815, 741, 853, 920, 751, 773, 648, 878, 751, 933, 692, 926, 813, 680, 943, 651, 683, 764, 907, 698, 894, 840, 931, 969, 714}

    {958, 823, 803, 652, 913, 814, 865, 891, 725, 659, 957, 705, 792, 781, 922, 917, 683, 673, 840, 966, 685, 710, 674, 948, 973, 923}

    {104, 984, 318, 117, 998, 457, 813, 491, 604, 641, 329, 216, 466, 343, 768, 245, 175, 354, 63, 118, 161, 14, 82, 994, 272, 932}

    Returns: 380.23999999999995

  47. 31

    {697, 807, 765, 889, 619, 688, 834, 705, 930, 762, 867, 674, 576, 834, 780, 726}

    {632, 926, 727, 569, 727, 873, 802, 652, 571, 552, 545, 661, 801, 698, 839, 893}

    {280, 691, 756, 777, 108, 699, 856, 802, 22, 883, 208, 542, 468, 789, 667, 242}

    Returns: 2466.7200000000003

  48. 27

    {806, 655, 651, 742, 615, 701, 602, 630, 601, 766, 563, 801, 625, 590, 749, 775, 737, 495, 612, 549, 752, 733, 636, 492, 700}

    {514, 476, 760, 505, 620, 595, 577, 591, 530, 515, 644, 563, 734, 737, 808, 612, 555, 608, 686, 515, 673, 687, 622, 526, 510}

    {26, 205, 567, 624, 185, 887, 521, 501, 368, 576, 362, 997, 332, 444, 2, 263, 63, 944, 348, 623, 908, 34, 926, 42, 106}

    Returns: 576.24

  49. 32

    {769, 762, 758, 690, 905, 842, 935, 704, 878, 639, 710, 676, 683, 942, 761, 915, 745, 795, 796, 790}

    {796, 723, 854, 662, 724, 569, 721, 583, 817, 700, 606, 609, 938, 953, 863, 757, 846, 801, 803, 817}

    {557, 262, 385, 461, 362, 677, 563, 566, 76, 642, 377, 409, 882, 881, 278, 980, 98, 576, 770, 558}

    Returns: 3100.7200000000003

  50. 38

    {905, 744, 997, 949, 845, 690, 814, 917, 916}

    {747, 962, 733, 905, 683, 789, 937, 865, 971}

    {784, 292, 278, 46, 459, 53, 973, 287, 856}

    Returns: 1121.4799999999998

  51. 11

    {197, 279, 308, 309, 244, 306, 202, 297, 302, 197, 261, 250, 279, 272, 232, 317, 326, 300, 268, 274, 281, 325, 203, 315, 318, 264, 210, 306, 233, 243, 258, 206, 321, 323, 280}

    {281, 269, 236, 223, 245, 272, 227, 294, 233, 290, 301, 330, 316, 249, 270, 216, 232, 273, 220, 305, 259, 231, 259, 257, 217, 302, 274, 239, 211, 251, 224, 232, 250, 200, 326}

    {770, 5, 338, 590, 789, 58, 860, 133, 90, 281, 32, 647, 56, 375, 7, 746, 592, 274, 301, 962, 970, 4, 909, 178, 471, 215, 989, 246, 324, 897, 981, 394, 959, 780, 317}

    Returns: 63.55999999999999

  52. 13

    {132, 179, 123, 144, 159, 145, 132, 207, 196, 191, 165, 132, 184, 178, 153, 184, 155, 192, 196, 163, 161, 127, 125, 171, 163, 146, 195, 143, 143, 196, 137, 174, 184, 143, 134, 132, 134, 190, 196, 205, 178, 166, 124, 189, 157, 195, 192, 187, 193}

    {145, 185, 123, 181, 130, 204, 153, 156, 136, 168, 165, 209, 158, 204, 181, 189, 135, 185, 153, 126, 123, 201, 184, 177, 132, 125, 143, 175, 193, 159, 129, 157, 154, 129, 154, 137, 135, 189, 204, 157, 178, 144, 193, 145, 142, 181, 132, 187, 128}

    {522, 366, 968, 880, 704, 395, 53, 118, 988, 564, 385, 311, 579, 836, 831, 497, 699, 328, 650, 840, 82, 262, 376, 177, 632, 92, 942, 323, 277, 189, 883, 825, 597, 455, 918, 31, 418, 690, 814, 415, 436, 501, 549, 421, 511, 218, 522, 447, 768}

    Returns: 0.0

  53. 41

    {825, 717, 913, 947, 868, 859, 898, 803, 754, 864, 767, 865, 932, 748, 965, 779, 982, 931, 735, 729, 797, 826, 776, 801, 996, 921, 772, 890}

    {725, 838, 815, 957, 800, 962, 811, 848, 744, 737, 811, 997, 801, 798, 981, 818, 801, 975, 958, 791, 929, 817, 999, 835, 993, 782, 985, 831}

    {786, 283, 136, 134, 208, 948, 544, 369, 458, 646, 719, 45, 104, 338, 291, 927, 55, 71, 466, 362, 214, 455, 560, 211, 193, 682, 619, 982}

    Returns: 1506.6000000000001

  54. 17

    {431, 488, 445, 328, 454, 381, 352, 370, 376, 449, 316, 478, 304, 378, 503, 394, 485, 303, 331, 406, 466, 342, 319, 412, 391, 324, 478, 427, 451, 491, 502, 455, 367}

    {358, 476, 386, 485, 301, 450, 466, 337, 381, 430, 429, 405, 446, 339, 304, 346, 308, 421, 331, 417, 459, 493, 461, 487, 320, 453, 298, 498, 448, 454, 309, 322, 415}

    {311, 906, 877, 887, 123, 418, 538, 582, 984, 237, 834, 948, 989, 738, 959, 40, 854, 969, 720, 795, 923, 433, 98, 448, 154, 695, 575, 855, 658, 897, 370, 983, 456}

    Returns: 504.00000000000006

  55. 27

    {776, 576, 554, 677, 739, 581, 687, 796, 691, 584, 667, 777, 549, 794, 500, 706, 571, 618, 737, 610, 536, 668, 508, 609, 534, 598, 775, 620, 778, 661}

    {582, 645, 595, 579, 496, 734, 581, 767, 545, 606, 619, 584, 485, 768, 641, 712, 607, 479, 658, 726, 751, 807, 750, 598, 613, 529, 767, 718, 731, 786}

    {175, 127, 478, 52, 222, 597, 534, 337, 522, 674, 714, 44, 340, 704, 391, 488, 86, 782, 448, 281, 577, 75, 351, 187, 655, 426, 100, 599, 540, 667}

    Returns: 1730.3199999999997

  56. 48

    {877, 939, 1000, 991, 978, 930, 949, 845, 961, 949, 886, 889, 946, 933, 898, 855, 983, 850, 856, 944, 991, 890, 907, 939, 934, 923, 910, 906, 977}

    {907, 939, 865, 964, 894, 958, 905, 900, 933, 957, 892, 854, 936, 858, 967, 939, 894, 998, 852, 994, 917, 869, 897, 846, 949, 895, 896, 892, 970}

    {927, 566, 219, 704, 86, 84, 201, 82, 944, 67, 383, 915, 944, 702, 817, 297, 293, 955, 449, 576, 709, 967, 163, 562, 393, 478, 369, 722, 920}

    Returns: 1787.5999999999997

  57. 23

    {538}

    {687}

    {492}

    Returns: 12792.0

  58. 100

    {10, 20, 30, 1000 }

    {30, 20, 10, 1000 }

    {423, 434, 445, 456 }

    Returns: 0.0

  59. 10

    {10, 20, 30, 1000 }

    {30, 20, 10, 1000 }

    {423, 434, 445, 456 }

    Returns: 0.0

  60. 10

    {240, 260 }

    {1000, 10 }

    {417, 233 }

    Returns: 16513.2

  61. 1

    {10, 20, 30, 1000 }

    {30, 20, 10, 1000 }

    {423, 434, 445, 456 }

    Returns: 253.80000000000004

  62. 10

    {2, 10 }

    {4, 250 }

    {200, 200 }

    Returns: 0.0

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: