El de la búsqueda binaria P89178


Statement
 

pdf   zip

thehtml

Estás de vacaciones en Estados Unidos, en una autopista en medio de la nada (pongamos, por ejemplo, Ohio), conduciendo uno de esos cochazos donde cabría un equipo de futbol americano entero. Aburrido, decides descubrir a qué velocidad constante debes mantener para alcanzar la siguiente gasolinera lo antes posible. Recuerda: a mayor velocidad, mayor consumo, por lo que si al llegar a la gasolinera te queda carburante, es que no ibas lo bastante rápido [Footnote: La OIE recomienda una conducción responsable en la vida real.].

En particular, sabes que tu vehículo consume

500 + ⌊ 
v+w
10
⌋ + ⌊
(v+w)2
100000

mililitros de carburante para recorrer un kilómetro, donde 0<v<30000 y −3000<w<3000 es la velocidad del vehículo y la fuerza del viento en centímetros por segundo, y los símbolos ⌊ · ⌋ quieren decir redondeo hacia abajo. (Ciertamente, estos coches americanos consumen mucho).

Se te pide que, dada la cantidad de carburante que tienes, el número de kilómetros que te separa de la gasolinera, y la intensidad del viento en cada uno de los kilómetros, digas a qué velocidad en centímetros por segundo deberías hacer todo el viaje para llegar lo antes posible a la gasolinera, sin quedarte sin carburante por el camino.

Entrada

Un juego de pruebas contiene varios casos, separados entre sí por una línea en blanco. Un caso viene descrito por varias líneas. La primera contiene dos números C<109 y n<103, separados por espacios, que describen la cantidad de carburante que tienes y el número de tramos que te separan de la gasolinera. Las siguientes n líneas describen un tramo de carretera, formado por un par de números di y wi, con la longitud en kilómetros y la fuerza del viento en el tramo i-ésimo. Se cumple que ∑i=1n di < 105. El consumo de carburante en cada kilómetro de un tramo debe calcularse individualmente, a efectos de los redondeos.

Salida

Para cada caso, escribe en una línea la velocidad en centímetros por segundo que te permitiría llegar antes a la gasolinera sin quedarte sin carburante por el camino. Se te garantiza que este numero es mayor que 0 y menor que 30000.



Pista: Búsqueda binaria es aquel invento que nos permite encontrar una palabra en el diccionario sin tener que leerlas todas.

Autor: 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
    

    Output

    10005
    12115
    14102
    
  • 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
    

    Output

    18888
    27923
    17362
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++