Autor | Zpráva | ||
---|---|---|---|
Ludolf Profil * |
#1 · Zasláno: 19. 12. 2012, 10:27:01
Zdravim, nedokázali by jste mi prosím někdo poradit s algoritmen na tento přiklad?
Musim to zapsat v pascalu a nějak nemužu přijit na algortimus. :( Účastníte se soutěže, ve které máte proti sobě sto soupeřů. Soutěž bude trvat k kol. V každém kole můžete některé soupeře vyřadit ze soutěže (vždy nejméně jednoho) a za jejich vyřazení dostanete odměnu. Odměna za vyřazení v soupeřů z počtu p je 100.000,- * v / p Počítáno v celých číslech (tzn. dolní celá část). Tedy například když v prvním kole vyřadíte 50 soupeřů z počátečních 100, získáte 50.000,-. Když ve druhém kole ze zbylých 50 vyřadíte 30, získáte 100.000,- * 30/50 = 60.000,- a máte celkem 110.000,- Když v posledním kole vyřadíte posledních 20 soupeřů, získáte 100.000,- * 20/20 = 100.000,- a váš celkový zisk bude 210.000,- Napište program, který pro zadaný počet kol určí a vytiskne maximální možný zisk a na další řádek počty soupeřů (oddělené mezerou), které máte vyřazovat v jednotlivých kolech. Příklad: Vstup: 3 Výstup: 280000 90 9 1 |
||
juriad Profil |
Dynamickým programováním, budeš uvažovat, kolik můžeš vydělat, pokud na začátku kola je N hráčů a zbývá K kol.
Budeš mít dvojrozměrné pole: pole[kola zbyvajici][hraci zbyvajici]. A ty budeš postupně dopočítávat postupně pole[0], pole[1], pole[2], ... -nekonecno reprezentuje stav, kdy nejde soutěž dohrát pole[0] bude obsahovat všude -nekonecno, kromě pole[0][0] = 0 for k in 1 .. K: // budeš vypočítávat pole[k] na základě pole[k-1] for n in 0 .. N: // budeš vypočítávat pole[k][n] na základě pole[k-1] max_odmena = -nekonecno for v in 0 .. n: // v tomto kole vyřadíš v lidí odmena_za_vyrazeni = 100000 * v/n odmena_za_dalsi_kola = pole[k-1][n-v] // nastaví max_odmena na maximum if max_odmena < odmena_za_vyrazeni + odmena_za_dalsi_kola max_odmena = odmena_za_vyrazeni + odmena_za_dalsi_kola pole[k][n] = max_odmena // vrátí maximální odměnu pro K kol a N lidí return pole[K][N] toto bez jako základ, zbytek si doplň - předvším posloupnost v vyřazení lidí, načítání vstupu, výpis výstupu, reprezentace -nekonečna
|
||
Ludolf Profil * |
#3 · Zasláno: 19. 12. 2012, 14:39:32
Diky, to pomohlo :)
|
||
Časová prodleva: 13 let
|
0