Programando el vídeo P39417


Statement
 

pdf   zip

thehtml

El profesor Oak es un gran seguidor de Humor Amarillo. Tanto, que se ha comprado una antena de satélite para ver el programa en varias cadenas europeas. El profesor Oak también tiene una guía de todos los canales de Europa, y quiere programar su vídeo para grabar cada día tantos episodios como sea posible. Pero no es tan fácil: el vídeo sólo puede grabar un canal a la vez. Además, los capítulos pueden tenir distintas duraciones (el modo en que están editados, la publicidad intercalada, etcétera).

Te pedimos que ayudes al profesor Oak. Haz un programa que, dado los minutos de inicio y de final de emisión de todos los episodios de Humor Amarillo en todos los canales europeos durante varios días, calcule y escriba el número máximo de episodios que puedan grabarse cada día. El aparato grabador necesita unos pocos segundos para parar la grabación y iniciar otra, por lo que no es posible grabar dos programas si uno de ellos empieza justo en el instante en el que acaba el otro.

Entrada

La entrada consiste en diversos casos. Cada caso tiene un natural n≥ 1, seguido de n pares (i1, f1), (i2, f2), …, (in, fn) de naturales que indiquen el minuto de inicio y el minuto de final (ambos inclusive) de cada capítulo de un día. Para todo j entre 1 y n se cumple 0 ≤ ijfj < 1440.

Salida

Para cada caso de entrada, escribe una línea con el número máximo de capítulos que el profesor Oak podrá grabar aquel día.

Puntuación

  • Test1:  ‍10 Puntos ‍

    Resolver una entrada con no más de 500 casos de n≤ 5.

  • Test2:  ‍10 Puntos ‍

    Resolver una entrada con no más de 500 casos de n≤ 10.

  • Test3:  ‍10 Puntos ‍

    Resolver una entrada con no más de 500 casos de n≤ 20.

  • Test4:  ‍10 Puntos ‍

    Resolver una entrada con no más de 500 casos de n≤ 50.

  • Test5:  ‍10 Puntos ‍

    Resolver una entrada con no más de 500 casos de n≤ 100.

  • Test6:  ‍10 Puntos ‍

    Resolver una entrada con no más de 20 casos de n≤ 500.

  • Test7:  ‍10 Puntos ‍

    Resolver una entrada con no más de 20 casos de n≤ 1000.

  • Test8:  ‍10 Puntos ‍

    Resolver una entrada con no más de 10 casos de n≤ 10000.

  • Test9:  ‍20 Puntos ‍

    Resolver una entrada con no más de 3 casos de n≤ 100000.

Public test cases
  • Input

    3     100 200   500 780   1000 1040
    
    7     400 1100   500 600   900 1400
          200 300   1200 1300   100 700
          800 1000
    
    3     0 100   100 1439   0 1439
    
    2     1234 1235   1235 1236
    

    Output

    3
    4
    1
    1
    
  • Information
    Author
    Ricardo Martín
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++