Entrades per grups al parc temàtic (DP) X46212

El parc temàtic de Tort Apenvura està muntant un esquema complicat d’entrades per grups, on el preu depèn de la grandària del grup. Tanmateix, es vol tenir en compte també factors específics com ara les grandàries de les taules dels restaurants i les capacitats simultànies de les atraccions; aixi, els preus no tenen realment una correlació amb les grandàries dels grups. Com que no veuen clar el desplegament del pla, han contractat la nostra amiga Mar Talavera, consultora free-lance, per a què els aconselli. Ella s’ha adonat que, amb l’esquema que plantegen, un grup de N persones, en comptes de pagar el preu fixat per un grup de grandària N, potser miren de separar-se en diversos grups més petits per tal de pagar menys.

Té la llista de preus per totes les grandàries de grup d’1 a N persones. Quina fora la manera més barata per a que hi entrin tots N?

Per exemple, suposem que els preus per grandària de grup, en euros i cèntims, són: 1: 25.50; 2: 45; 3: 68; 4: 99.50; i 5: 130. Aleshores, encara que a un grup de 5 se’ls demana pagar 130, aquestes 5 persones poden entrar amb entrades individuals per 5*25.50 = 127.50, o fer dues parelles i un individu per 115.50 o, encara millor, dividir-se en un grup de 3 i un altre de 2 i pagar només 113, que és, de fet, el preu més barat per un grup de 5.

Entrada

Les dades comencen amb N > 0: la màxima grandària de grup a la que s’aplica l’esquema de preus. A la línia següent segueix la llista de preus, N floats: quant es demana per un grup de k persones, per k d’1 fins a N. Aquests valors venen separats per espais en blanc en una sola línia d’entrada.

Sortida

El cost de la manera més barata per entrar N persones, expressat amb dues places decimals: euros i cèntims. (La correcció automàtica no voldrà veure com es divideix el grup per tal d’obtenir el cost més reduït. Però, ulls humans que puguin llegir el teu programa probablement valoraran positivament l’evidència de que el programa pot ser canviat molt fàcilment per tal que proporcioni aquesta informació.)

Observació

Cal fer servir un esquema de Programació Dinàmica per resoldre aquest problema. El problema X55205 demana una solució per backtracking del mateix problema.