Statistics

Problem Statement for "CircleHighway"

Problem Statement

The Siberian Highway starts at Samovar Village and goes for 1000 kilometers (km) in a circle. It is a one lane highway and the driving is allowed only one way: in the clockwise direction. Your car has enough tank capacity for exactly 500 km. There are ten gas stations on this highway, and they are running out of gas. You know that, at the beginning, the total amount of gas in all gas stations and in your tank is exactly enough for 1000 km. You will be given the distances from Samovar village to each of the gas stations in the clockwise direction in millimeters. (1 km = 1000 meters (m), 1 meter = 1000 millimeters (mm)). You will be given the amount of gas available at each gas station and the amount of gas in your tank before you start, also in millimeters (meaning the number of millimeters you can drive with it).

Your task is to determine the closest point to Samovar Village in the clockwise direction from which you can start the car and drive a full circle around this Highway. You will be given a int[] distances and a int[] gas, where element i of distances is the clockwise distance from the village to gas station i in millimeters, and element i of gas is the number of millimeters worth of gas available at gas station i. You will also be given an int, yourGas, representing the number of millimeters of gas you already have in your tank. Since there is exactly enough gas to drive 1000 km, you will have to stop at every gas station you pass and take all of the gas available if you hope to drive the full 1000 km. However, since your tank will only hold 500 km worth of gas, this will not always be possible. If it is impossible to drive around the full circle from any starting point, your method should return -1.

Definition

Class:
CircleHighway
Method:
closest
Parameters:
int[], int[], int
Returns:
int
Method signature:
int closest(int[] distances, int[] gas, int yourGas)
(be sure your method is public)

Notes

  • You are not allowed to take more gas with you than you can fit in your tank.
  • The gas stations all have zero effective width, so they can be jammed together only a millimeter apart.

Constraints

  • distances and gas have exactly ten elements each
  • each element of distances is between 0 and 999,999,999 inclusive.
  • elements of distances are distinct and given in increasing order
  • each element of gas is between 0 and 1,000,000,000 inclusive
  • yourGas is between 0 and 500,000,000 inclusive
  • the total sum of all elements of gas and yourGas is 1,000,000,000

Examples

  1. {1,5,100,101,1000,2000,3000,4000,5000,6000}

    {0,1000000000,0,0,0,0,0,0,0,0}

    0

    Returns: -1

    The only place where you could possibly start driving is the second station. But you can't fit all the gas into your tank, so the gas would be enough for you to drive only half the circle. Return -1

  2. {1,5,100,101,1000,2000,3000,4000,5000,6000}

    {0,0,500000000,0,0,0,0,500000000,0,0}

    0

    Returns: -1

    If you start driving at the third station then when you reach the eighth station you would not be able to fit all the gas from that station into your tank. If you start at the eighth station you wouldn't have enough gas to reach the third one. Return -1.

  3. {100,200,1000,2000,3000,4000,5000,500001000,600000000,699999999}

    {0,0,500000000,0,0,0,0,500000000,0,0}

    0

    Returns: 1000

    We can start from the third or from the eighth gas station and drive the full circle. The third station is closer clockwise. Return 1000.

  4. {100,200,1000,2000,3000,4000,5000,500001000,600000000,699999999}

    {0,0,500000000,0,0,0,0,499999975,0,0}

    25

    Returns: 975

  5. {100,200,1000,2000,3000,4000,5000,500001000,600000000,699999999}

    {0,0,0,0,0,0,0,500000000,0,0}

    500000000

    Returns: 1000

  6. {1,100000001,200000001,300000001,400000001, 500000001,600000001,700000001,800000001,900000001}

    {100000000,100000000,100000000,100000000,100000000,100000000, 100000000,100000000,100000000,100000000}

    0

    Returns: 1

  7. {1,100000001,200000001,300000001,400000001,500000001,600000001,700000001,800000001,900000001}

    {0,0,0,0,0,0,0,200000000,0,300000000}

    500000000

    Returns: 200000001

  8. {0,1,2,3,499999999,500000000,600000000,700000000,800000000,900000000}

    {0,0,0,0,500000000,0,0,0,0,0}

    500000000

    Returns: 999999999

  9. {70699724, 87990049, 127020956, 259368632, 372617857, 611840178, 660673492, 705812839, 742912632, 802765530}

    {39161827, 34136899, 81095167, 93463288, 79287128, 34184745, 52136581, 64925470, 68272380, 3093060}

    450243455

    Returns: 0

  10. {70699724, 87990049, 127020956, 259368632, 372617857, 611840178, 660673492, 705812839, 742912632, 802765530}

    {39161827, 34136899, 81095167, 93463288, 79287128, 34184745, 52136581, 64925470, 68272380, 403093060}

    50243455

    Returns: 576245292

  11. {14429004, 116777856, 183545915, 268867978, 330253717, 371106765, 633521108, 910770882, 916652817, 973182828}

    {157663483, 13231632, 76303504, 19502727, 18931298, 176836627, 122572544, 122455243, 17943800, 177029817}

    97529325

    Returns: 813241557

  12. {100,500000101, 500000102,500000103,500000104,500000105, 500000106,500000107,500000108,500000109}

    {499999990,499999911,0,0,0,0,0,0,0,0}

    99

    Returns: 500000090

  13. {70699724, 87990049, 127020956, 259368632, 372617857, 611840178, 660673492, 705812839, 742912632, 802765530}

    {157663483, 13231632, 76303504, 19502727, 18931298, 176836627, 122572544, 122455243, 17943800, 177029817}

    97529325

    Returns: 514310853

  14. {14001234,25790093,29205405,133628031,216203501, 241968487,335747855,358411989,409099026,436935534}

    {41068575,102880168,22811826,60528045,52885843, 54609765,161190371,98070914,112850585,185668492}

    107435416

    Returns: 906565818

  15. {2864559, 89137045, 90819780, 139847153, 194902081, 254876142, 272010910, 681460264, 960546278, 991840723}

    {137281297, 26249605, 25618392, 41239092, 46405836, 123444534, 30878710, 132837489, 103231774, 87256471}

    245556800

    Returns: 582151989

  16. {113796061, 174830941, 208267338, 299859469, 473118703, 529204981, 664024379, 754174772, 767456423, 997624447}

    {68150737, 50605938, 82079622, 98768845, 17760670, 82401702, 8240759, 41501476, 93671992, 69996215}

    386822044

    Returns: 67620662

  17. {20568091, 33488019, 40612029, 74231137, 163658441, 196629021, 718650351, 866126674, 940212890, 945606840}

    {38569018, 56674937, 33733507, 61225416, 55842157, 24182239, 74453285, 54520218, 34733972, 77640937}

    488424314

    Returns: 322815073

  18. {20568091, 33488019, 40612029, 74231137, 163658441, 196629021, 718650351, 866126674, 940212890, 945606840}

    {64050477, 92204530, 91665091, 78855096, 65102590, 89989216, 38990349, 93012125, 98172229, 59553969}

    228404328

    Returns: 598731997

  19. {20568091, 33488019, 40612029, 74231137, 163658441, 196629021, 718650351, 866126674, 940212890, 945606840}

    {50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000}

    500000000

    Returns: 340212890

  20. {70000000, 170000000, 270000000, 370000000, 470000000, 570000000, 670000000, 770000000, 870000000, 970000000}

    {50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000}

    500000000

    Returns: 20000000

  21. {70000000, 170000000, 270000000, 370000000, 470000000, 570000000, 670000000, 770000000, 870000000, 970000000}

    {50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 100000000, 0}

    500000000

    Returns: 0

  22. {70000000, 170000000, 270000000, 370000000, 470000000, 570000000, 670000000, 770000000, 870000000, 970000000}

    {100000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 0}

    500000000

    Returns: 220000000

  23. {70000000, 170000000, 270000000, 370000000, 470000000, 570000000, 670000000, 770000000, 870000000, 970000000}

    {50000000, 100000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 0}

    500000000

    Returns: 0

  24. { 0, 50000000, 100000000, 150000000, 200000000, 250000000, 300000000, 350000000, 400000000, 450000000 }

    { 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000 }

    500000000

    Returns: 500000000

  25. { 1, 100000001, 200000001, 300000001, 400000001, 500000001, 600000001, 700000001, 800000001, 900000001 }

    { 100000000, 100000000, 100000000, 100000000, 100000000, 100000000, 100000000, 100000000, 100000000, 100000000 }

    0

    Returns: 1

  26. { 0, 1, 2, 3, 499999999, 500000000, 600000000, 700000000, 800000000, 900000000 }

    { 0, 0, 0, 0, 500000000, 0, 0, 0, 0, 0 }

    500000000

    Returns: 999999999

  27. { 2, 200000000, 300000000, 400000000, 500000000, 600000000, 700000000, 800000000, 900000000, 950000000 }

    { 0, 49999999, 100000000, 100000000, 100000000, 100000000, 100000000, 100000000, 100000001, 100000000 }

    150000000

    Returns: 100000001

  28. { 14001234, 25790093, 29205405, 133628031, 216203501, 241968487, 335747855, 358477989, 409099026, 436935534 }

    { 41068575, 102880168, 22811826, 60528045, 52885843, 54609765, 161190371, 98070914, 112850585, 185668492 }

    107435416

    Returns: 906565818

  29. { 10, 20, 30, 40, 50, 60, 70, 80, 90, 500000010 }

    { 499999999, 0, 0, 0, 0, 0, 0, 0, 0, 500000000 }

    1

    Returns: 10

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: