Juegos de Video

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Leonardo

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

¡A las vacas del Granjero Juan les gustan mucho sus juegos de video! GJ se dio cuenta que después de jugar estos juegos sus vacas producen mucha más leche que lo usual, seguramente debido a que vacas contentas hacen mas leche.

Sin embargo, las vacas no están de acuerdo, en cuál es el mejor juego de consola. Una vaca quería comprar la Xbox Series X para jugar Assassins Creed Valhalla ; otra quería comprar el Nintendo Switch para jugar Zelda Breath of the Wild ; una tercera quería jugar Spiderman Miles Morales en la PlayStation 5. GJ quiere comprar un conjunto de consolas de juego y juegos (dentro de las restricciones de un presupuesto dado) que ayude a sus vacas a producir la mejor leche y por lo tanto alimentar a más niños.

GJ investigó $N (1 \leq N \leq 50)$ ~N (1 \leq N \leq 50)~ consolas, cada una con un precio de consola $P_i (1 \leq P_i \leq 1000)$ ~P_i (1 \leq P_i \leq 1000)~ y un número de juegos específicos de consola $G_i (1 \leq G_i \leq 10)$ ~G_i (1 \leq G_i \leq 10)~. Una vaca debe, por supuesto, tener una consola antes de que ella pueda comprar cualquier juego que sea especifico para esa consola. Cada juego individual tiene un precio de juego $GP_j (1 \leq GP_j \leq 100)$ ~GP_j (1 \leq GP_j \leq 100)~ y un valor de producción $(1 \leq VP_j \leq 1,000,000)$ ~(1 \leq VP_j \leq 1,000,000)~, el cual indica cuánta leche producirá una vaca después de jugar el juego. Finalmente, el Granjero Juan tiene un presupuesto $V (1 \leq V \leq 100,000)$ ~V (1 \leq V \leq 100,000)~ el cual indica la cantidad máxima de dinero que él puede gastar. Ayúdelo a maximizar la suma de valores de producción de los juegos que él compre.

Considere un juego de datos con $N=3$ ~N=3~ consolas y un presupuesto $V=$800$ ~V=$800~. La primera consola cuesta $$300$ ~$300~ y tiene dos juegos con costos $$30$ ~$30~ y $$25$ ~$25~ y valores de producción como se muestra:

Juego #  Costo    Valor de Producción
  1       $30          50
  2       $25          80

La segunda consola cuesta $$600$ ~$600~ y tiene únicamente $1$ ~1~ juego:

Juego #  Costo    Valor de Producción
  1       $50          130

La tercera consola cuesta $$400$ ~$400~ y tiene $3$ ~3~ juegos:

Juego #  Costo    Valor de Producción
  1       $40         70
  2       $30         40
  3       $35         60

El Granjero Juan debería comprar las consolas $1$ ~1~ y $3$ ~3~, juego $2$ ~2~ para la consola $1$ ~1~, y juegos $1$ ~1~ y $3$ ~3~ para la consola $3$ ~3~ para maximizar su producción esperada en $210$ ~210~:

                          Valor de Producción
  Presupuesto:    $800      
      Consola 1  -$300
      Juego 2   -$25              80
      Consola 3  -$400
      Juego 1   -$40              70
      Juego 3   -$35              60
  -------------------------------------------
    Total:         0 (>= 0)      210

Entrada

Línea $1$ ~1~: Dos enteros separados por espacio: $N$ ~N~ y $V$ ~V~ Líneas $2..N+1$ ~2..N+1~: La línea $i+1$ ~i+1~ describe el precio de la i-esima consola y de los juegos disponibles para la consola $i$ ~i~; contiene: $P_i$ ~P_i~, $G_i$ ~ G_i~, y $G_i$ ~G_i~ pares de enteros separados por espacios $GP_j$ ~GP_j~, $PV_j$ ~ PV_j~

Salida

Línea $1$ ~1~: El valor máximo de producción que el Granjero Juan puede obtener con su presupuesto

Ejemplo de Entrada

3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60

Ejemplo de Salida

Comments

1

hohemhein commented on April 22, 2021, 7:45 p.m.

El problema fue quitado del la pagina usaco solo aparecen los problemas de 2011 en adelante?

1

Osnielfc_07 commented on April 22, 2021, 7:04 p.m. ← edit 4 →

Men , este ejrcicio es un Usaco de oro del mes de Diciembre del año ( 2009 - 2010 ) , ahi puedes ver la explicación del problema y un codigo con la solucion . Saludos para todos los usuarios.

1

hohemhein commented on April 22, 2021, 2:58 p.m.

Alguien puede explicarme la solucion de este ejercicio por favor?