Velocirráptors 301 P88665


Statement
 

pdf   zip

thehtml

Cuando sales del lavabo para volver a clase descubres que una manada de velocirráptors ha entrado en las aulas y ha devorado a tus compañeros. El pasillo donde estás está cerrado: imposible huir. Los velocirráptors, dentro de las aulas haciendo la digestión, saldrán en cualquier momento para acabar contigo. En fin, ya se sabe que estas cosas pasan.

El pasillo de tu instituto se representa por un segmento de la recta real que va del 0 al 2n−2, con n puertas que dan a n aulas, situadas sobre los puntos 0, 2, 4, …, 2n−2 de la recta. El lavabo del que sales está situado en el punto k con 0≤ k ≤ 2n−2 y k par. Tanto tú como los velocirráptors tardáis 1 segundo en recorrer una unidad de distancia sobre la recta (los velocirráptors ya están satisfechos y no están dispuestos a correr más por un triste postre).

Se te pide que, asumiendo que conoces qué velocirráptors saldrán de sus aulas a por tí y en qué instantes de tiempo ti lo harán, y asumiendo también que estos se dirigirán hacia ti (estés donde estés) nada más salir, digas cuántos segundos puedes alargar tu (breve pero intenso) tiempo de vida realizando los movimientos acertados.

[r]

Creemos que te resultará muy útil pensar en diagramas espacio-temporales como el de la derecha, donde se ejemplifica una posible situación para k=6 y n=11, donde 3 velocirráptors salen de las aulas situadas en los puntos 2, 4 y 14 en los instantes 6, 10 y 8 respectivamente. La respuesta correcta en este caso es 13.

Entrada

Un juego de pruebas contiene varios casos. Cada caso empieza con tres naturales n, m y k, con 0≤ k≤ 2n−2, 1≤ n≤ 108 y 1≤ m ≤ 10000, donde n y k son como se describe en el enunciado y m es el número de velocirráptors. Las siguientes m líneas de la entrada contienen un par de números ai, ti, donde ai es el aula que se ha zampado el i-ésimo velocirráptor y ti el instante de tiempo en el que saldrá a por su postre. Se cumple que 0≤ ai≤ 2n−2 y 0≤ ti≤ 109 para todo i, que ai y ti son pares, y que todos los ai son distintos.

Salida

Para cada caso, escribe en una línea el tiempo que puedes alargar tu vida. Que los tiempos ti y las aulas ai sean números pares garantiza que la respuesta siempre será un entero.

Puntuación

  • Test1:  ‍45 Puntos ‍

    Pruebas con no más de 20 casos con n=m ≤ 100 y donde los ai aparecen ordenados (como el ejemplo 1).

  • Test2:  ‍30 Puntos ‍

    Pruebas con no más de 20 casos con n≤ 1000 y m≤ 100 (como los ejemplos 2 y 3).

  • Test3:  ‍25 Puntos ‍

    Pruebas con no más de 20 casos de n≤ 108 y m≤ 104 (como el ejemplo 4).

Public test cases
  • Input

    5 5 4
    0 0
    2 2
    4 4
    6 2
    8 0
    
    5 5 4
    0 0
    2 2
    4 6
    6 2
    8 0
    
    5 5 4
    0 0
    2 6
    4 6
    6 6
    8 0
    
    5 5 4
    0 20
    2 2
    4 20
    6 20
    8 20
    
    5 5 4
    0 2
    2 20
    4 20
    6 20
    8 0
    
    5 5 4
    0 2
    2 4
    4 0
    6 2
    8 2
    
    5 5 0
    0 2
    2 0
    4 10
    6 10
    8 10
    
    3 3 2
    0 10
    2 10
    4 10
    

    Output

    4
    4
    4
    8
    5
    0
    2
    11
    
  • Input

    11 3 6
    2 6
    4 10
    14 8
    

    Output

    13
    
  • Input

    1000 1 0
    100 100
    
    1000 1 0
    100 98
    
    540 5 482
    508 1064
    392 286
    472 338
    186 818
    62 840
    
    43 2 0
    24 72
    44 44
    
    90 7 18
    68 112
    34 84
    8 16
    82 82
    24 60
    52 152
    36 28
    

    Output

    200
    198
    944
    88
    170
    
  • Input

    50000000 7 67958422
    87401816 62889408
    6968110 151700716
    72342116 155469888
    89165870 73851810
    94055040 7972090
    34446444 32438808
    11204152 4411784
    
    50000000 10 54159472
    16811258 75071762
    82396964 125722710
    45739798 94247702
    8034262 18999860
    36992544 92063428
    87918930 66633664
    82468966 168041758
    40581626 31570418
    50437158 161755152
    19037120 148790458
    

    Output

    47617381
    78714732
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++