| 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: 6 let
|
|||