Autor Zpráva
Ludolf
Profil *
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 *
Diky, to pomohlo :)

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0