The one of the binary search P89178


pdf   zip


You are on holidays in the United States, in a highway in the middle of nothing (for instance, Ohio), driving one of those big cars where a whole football team would fit. Bored, you decide to discover what contanst speed you must mantain to reach the next petrol station as soon as possible. Remember: the greater the speed is, the greater the consumption is, so if when you arrive to the petrol station the car has still fuel, it means that you did not go fast enough [Footnote: OIE recommends a responsible driving in the real life.].

In particular, you know that your vehicle consumes

500 + ⌊ 
⌋ + ⌊

millilitres of fuel to go around a kilometre, where 0<v<30000 and −3000<w<3000 is the speed of the vehicle and the power of the wind in centimetres per second, and the symbols ⌊ · ⌋ mean round towards zero. (Certainly, these american cars consume a lot).

You are asked to, given the quantity of fuel that you have, the number of kilometres of distance to the petrol station, and the intensity of the wind in each one of the kilometres, say what speed in centimetres per second you should go all the travel to reach as soon as possible the petrol station, without being with no fuel during the travel.


A test data contains various cases, separated by a line in white. A case is described by various lines. The first one contains two numbers C<109 and n<103, separated by spaces, that describe the quantity of fuel tha you have and the number of stretches that separe you from the petrol station. The following n lines describe a road stretch, formed by a pair of numbers di and wi, with the length in kilometres and the power of the wind in the i-th strecth. It is fulfilled that ∑i=1n di < 105. The consumption of fuel in each kilometre of a stretch must be computed individually, to avoid rounding problems.


For each case, your program must print in a line the speed in centimetre per second that would allow you to reach before to the petrol station without being with no fuel during the travel. We assure you that this number is greater than 0 and less tan 30000.

Hint: Binary search is that invent that allow us to find a word in the dictionary without reading all the words.

Author: Ricardo Martín, Omer Giménez.

Public test cases
  • Input

    25329 3
    7 -776
    3 -627
    1 -114
    24208 3
    5 -262
    2 -676
    1 -956
    38454 5
    2 -85
    2 -840
    3 -260
    2 527
    1 127


  • Input

    5065527 6
    147 -1552
    61 -1254
    94 -531
    162 1940
    101 -742
    270 1034
    5733043 1
    512 166
    3967428 6
    118 -1803
    71 -929
    27 -981
    140 372
    3 322
    420 -77


  • Information
    Omer Giménez
    Carlos Molina
    Original language
    Other languages
    Official solutions
    User solutions