Salchichas (2) P72625


Statement
 

pdf   zip

thehtml

¡El carnicero de las salchichas vuelve a la carga! Esta vez tiene N pedidos distintos, donde cada cliente ha pedido entre mi y Mi salchichas, con mi<Mi. El cliente acabará satisfecho únicamente si recibe Mi salchichas. Si recibe entre mi y Mi−1, el cliente no estará contento, pero la sangre no llegará al río. Por contra, si recibe menos de mi salchichas, el cliente llevará al carnicero a los tribunales.

Se te pide que calcules el máximo número de clientes satisfechos que el carnicero puede conseguir sin que nadie llegue a denunciarlo. insatisfechos.

Entrada

Cada entrada contiene como mucho 5 casos. La primera línea contiene el número N de clientes y la cantidad total T de salchichas. La segunda línea contiene los 2N valores m1, M1, m2, M2, …, mN, MN, con un espacio de separacion entre mi y Mi, y dos espacios de separación entre Mi y mi+1.

Salida

Para cada caso de pruebas, escribe una línea con la máxima cantidad de clientes que es posible satisfacer sin recibir ninguna denuncia.

Puntuación

  • TestA:  ‍ Entradas con N=1.  ‍20 Puntos ‍
  • TestB:  ‍ Entradas con N=2.  ‍20 Puntos ‍
  • TestC:  ‍ Entradas con N=3.  ‍20 Puntos ‍
  • TestD:  ‍ Entradas con N≤ 1000.  ‍20 Puntos ‍
  • TestE:  ‍ Entradas con N≤ 100000.  ‍20 Puntos ‍
Public test cases
  • Input

    1 10
    5 10
    

    Output

    1
    
  • Input

    1 10
    6 11
    

    Output

    0
    
  • Input

    3 10
    1 3  2 4  11 12
    

    Output

    0
    
  • Input

    4 100
    10 20  20 30  30 40  25 26
    

    Output

    2
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++