Comedor escolar P52658


Statement
 

pdf   zip

html

El encargado de un comedor escolar tiene que equilibrar el presupuesto para poder servir comidas a tantos niños como sea posible. Por ejemplo, si el presupuesto consta de T=1000 euros, una ensalada cuesta 2 euros y un bistec cuesta 6 euros, el encargado puede usar el presupuesto para comprar 500 ensaladas y 0 bistecs, o 497 ensaladas y 1 bistec, o 494 ensaladas y 2 bistecs, o 2 ensaladas y 166 bistecs, etc. Sabiendo que cada niño necesita una ración de cada uno de los platos, se te pide que calcules para cuántos niños da el presupuesto. En el ejemplo anterior la respuesta es 125, puesto que es posible servir 125 ensaladas y 125 bistecs (en este ejemplo no sobra ningún euro, pero en general puede sobrar dinero).

Entrada

Una línea con el número N>0 de casos. La primera línea de cada caso contiene el número 0≤ T≤ 105 de euros de presupuesto, y el número K de platos distintos. La línea siguiente contiene K números entre 1 y 105, con el coste de una ración de cada uno de los K platos.

Salida

Escribe una línea para cada caso, con el número máximo de raciones completas (con un plato de cada tipo) que es posible servir con el presupuesto dado.

Puntuación

  • TestA:   Resolver casos con K=1.  20 Puntos 
  • TestB:   Resolver casos con K=2.  20 Puntos 
  • TestC:   Resolver casos con K=3.  25 Puntos 
  • TestD:   Resolver casos con K≤ 10.  35 Puntos 
Public test cases
  • Input

    1
    200 1
    57
    

    Output

    3
    
  • Input

    3
    1000 2
    2 6
    1000 2
    17 21
    1000 2
    1 100
    

    Output

    125
    26
    9
    
  • Input

    1
    99000 5
    7 1025 30 1 150
    

    Output

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