Meno: Michal Korbela
Škola: Gybmnázium J.J. Bánovce nad B. Radlinského 665/2, 95701
Adresa domov: Brezolupy 160, 95701
Trieda: kvinta
Úloha č.3 - Popis




Tu si musíme uvedomiť, že nás nejaújíma čas, za koľko sa tam jednotky dostanú.
Ak sa tam nejaké jednotky dostanú, tak to bude nejaká kombinácia jednotiek.
To znamená, že nám stačí otestovať, či nájdeme takú kombináciu, ktorej súčet prvkov je väčší ako predchádzajúcej a to najviac o najväčší denný prírastok. Ak však takúto kombináciu nenájdeme, tak sa bude hľadať o 1 menšia, a to až dovtedy, kým nebude hodnota súčtu kombinácie rovná počtu obsadených vojakov.

Časová zložitosť škoda , ale O(N^5) pretože kombinácie nám zaberú veľa času(sú tam vnorené 4 cykly, preto n^4) a testujeme ich n krát - n^5
Pamäťová zložitosť - musíme si zapamätať všetky jednotky - O(n)