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
Je to len matematický zápis (100.000,- * v / p)... Sleduješ v premenných aká je odmena, koľko zostalo, koľko si vyradil... Nič zložité.
Programovať vieš, alebo s čím konkrétne máš problém?
Programovat umim, jen nemužu přijit na ten algoritmus abych ziskal maximalni možny zisk dle zadaných počtu kol. Mohl by si to vic popsat nebo ukazat prosimtě?
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.)