De compras RPG P43961

Statement

html

Después de una dura jornada matando monstruos en los calabozos de nivel 40, ha llegado el momento de las compras. Cuentas todo el oro conseguido, te acercas al tendero del pueblo y miras la hoja de precios...

Tu personaje sólo puede llevar exactamente cuatro objetos encima: un arma, un yelmo, una coraza y un brazalete. Cada uno de estos objetos te aporta unos beneficios, o puntos, de tres tipos: puntos de ataque, puntos de defensa, o puntos de magia. Se te pide que escribas un programa que, dada la lista de precios, decida cómo invertir el oro ganado para equipar a tu personaje con objetos que maximicen la suma de estos tres tipos de puntos.

Entrada

La primera línea contiene dos naturales g y n, donde 1≤ g≤ 100 es el número de monedas de oro de que dispones y 1≤ n≤ 2500 el número de objetos que hay en la tienda. A continuación, n líneas, cada una de las cuales siguiedo el formato t N p a d m, donde t es un carácter que indica el tipo de objeto (’A’, ’Y’, ’C’, ’B’), N es una secuencia de como mucho 20 letras mayúsculas con el nombre del objeto, p es su precio en monedas de oro, y a, d y m son números enteros que indican los puntos de ataque, defensa y magia que confiere la posesión del objeto.

Tu programa deberá resolver 30 entradas como las descritas en un tiempo de 1 segundo.

Salida

Encuentra qué objetos debes comprar, sin haber más de uno de cada tipo, para maximizar la suma de puntos de ataque, defena y magia; en caso de haber más de una combinación óptima, escribe aquella que sea más barata. Los datos de entrada serán tales que sólo existirá una única combinación con esta propiedad.

En concreto, tu programa deberá escribir dos líneas. En la primera línea, separados por espacios, deberás escribir los nombres del arma, yelmo, coraza y brazalete que has elegido, o “NADA” si no compras objeto de algún tipo. En la seguna línea, también separados por espacios, escribe los puntos de ataque, defensa y magia que te otorga la combinación elegida.

Public test cases

Input

100 8
A DAGA 10 3 0 0
A ESPADA 20 5 2 0
A ESPADAMAGICA 50 4 3 3
Y CASCOCUTRE 5 0 2 0
Y GORRITOMAGICO 30 0 1 2
Y SUPERYELMO 120 0 100 0
C ARMADURACUERO 40 0 10 0
B BRAZALETENEGRO 80 0 0 5

Output

ESPADAMAGICA CASCOCUTRE ARMADURACUERO NADA
4 15 3

Input

19 3
A ESPADA 20 5 2 0
Y GORRITOMAGICO 30 0 1 2
C ARMADURACUERO 40 0 10 0

Output

NADA NADA NADA NADA
0 0 0

Input

39 25
A PUPMDNFE 51 19 -9 18
B SKDMRPWB 26 14 4 4
C ZWHMCNN 45 17 8 7
C VIDPISMWPUK 20 -10 -5 -1
C YQLIYKBV 41 1 6 11
A PIWUWYLU 29 11 15 3
B HZRBHISVVTUZ 40 13 1 -10
Y ODHISMYJ 42 -2 -9 9
Y PQMJZJGPNBB 46 3 6 -5
B WPZTAAQPEBBP 46 19 12 18
B SPADWUCKD 17 2 0 8
A VSOSBCBHTB 49 -6 17 0
A NVKRDXCUOV 32 -10 15 3
A RXFCDIZP 33 7 5 19
C NDODWKEKSQCV 19 17 18 -4
B SHGBIX 43 -4 19 3
B HPZMKFJA 23 0 3 -7
C QHTEDVHWNLA 23 -5 4 14
C EOSQNHHE 38 6 10 3
Y ZCTKUTFUPQ 21 7 8 20
Y ETDAUIWJLZL 33 12 4 -3
B FLXNNCHDVIMH 19 -4 -8 9
B RQSCMKBGS 19 16 -7 12
A CVAYBW 33 10 -1 0
A YIDXPAB 48 0 9 5

Output

NADA NADA NDODWKEKSQCV RQSCMKBGS
33 11 8

Information

Author: Omer Giménez
Language: Spanish
Other languages: English
Official solutions: C++
User solutions: C++