Algoritmus soutěže
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
Dá sa to dynamickým programovaním
V prvom kroku vypočítaš (triviálne) najlepšie stratégie a maximálne zisky pre posledné kolo a počty (zostávajúcich) súperov od 1 do 100. Uložíš to do poľa (alebo 2 polí).
S využitím týchto dát, následne vypočítaš to isté pre 2 posledné kolá (zase budeš mať pole stratégií a maximálnych ziskov pre 1 až 100 súperov).
Potom pre 3 kolá, 4 kolá, atď až kým sa dostaneš k potrebnému počtu kôl. (Pri výpočte (i+1)-teho kola od konca sa využijú výsledky pre i.)