Cassete P65849


Statement
 

pdf   zip

thehtml

Tenéis una cassete con t segundos de duración, y n canciones con duraciones d1, d2, …, dn. Vuestro objetivo es guardar el máximo número de canciones enteras en la cassete. Debéis tener en cuenta que las canciones deben grabarse con un segundo de separación entre ellas.

Entrada

La entrada consiste en una serie de casos separados con una línea en blanco. Cada caso consiste en dos líneas: La primera tiene t y n. La segunda tiene n números: d1, d2, …, dn. Podéis asumir 1 ≤ t ≤ 108, n ≥ 1, y que para cada i, 1 ≤ di ≤ 106.

Salida

Para cada caso de la entrada, hay que escribir el número máximo de canciones que caben enteras en la cassete, teniendo en cuenta que deben separarse con un segundo.

Puntuación

  • TestA:  ‍ En algunos juegos de pruebas se cumplirá n ≤ 100.  ‍60 Puntos ‍
  • TestB:  ‍ Otros juegos de pruebas incluirán casos con n ≤ 105.  ‍40 Puntos ‍
Public test cases
  • Input

    11 5
    2 2 2 2 2
    
    10 5
    2 2 2 2 2
    
    100 1
    101
    
    1000 3
    17 1 17
    

    Output

    4
    3
    0
    3
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++