Tot fent un cop de mà a la terrissaire (DP) X52116

La nostra estimada amiga Coràlia Belet és terrissaire. Disposa ara de N grapats d’argila. Aquesta temporada fa bols de diverses mides: amb un grapat d’argila, o dos, o tres... per bol, fins a N, quan fa el bol més gran. Té una llista amb els guanys que li produeix la venda de cada grandària de bol, d’1 a N; el guany d’un bol, tanmateix, no es correspon gaire amb quants grapats d’argila s’han emprat per fer-lo: amb els grossos, a més de la major despesa d’argila, s’hi presenten dificultats en tornejar-lo, però, també és difícil, per altres raons, fer-los petitons i macos. Li cal un consell avui: com distribuïrà els N grapats d’argila que té per fer bols, per tal d’aconseguir el màxim guany? Volem fer un programa que li ajudi.

Exemple: amb 5 grapats, si els guanys, en euros i cèntims, son: 1: 25; 2: 60; 3: 75; 4: 100; i 5: 112.50, el màxim guany és 145.00 euros; ho assoleix si fa un bol d’1 grapat i 2 bols de 2 grapats.

Entrada

Les dades comencen per N > 0: quants grapats d’argila cal distribuir avui. Segueix la llista de guanys, N floats: quant guanya na Coràlia amb la venda d’un bol fet amb k grapats d’argila, per k d’1 fins a N, expressat amb dos decimals (euros i cèntims). Aquestes dades venen separades per espais i/o tabuladors i/o canvis de línia, és a dir, poden aparèixer, o no, a la mateixa línia d’entrada.

Sortida

El màxim guany que pot obtenir na Coràlia avui, expressat amb dos decimals: euros i cèntims. (Encara que no s’hagi d’escriure com s’assoleix aquest guany per la correcció automàtica, el corrector humà valorarà positivament que el programa que s’envia al Jutge pugui escriure molt fàcilment aquesta informació.)

Observació

Cal aplicar un esquema de programació dinàmica. El problema bessó X33098 consisteix a resoldre exactament el mateix enunciat amb un esquema de backtracking.