Štafeta

  • Na prvý pohľad nevidno spôsob riešenia, ale vedeli ste, že ide o dynamické programovanie.
  • Vedeli by ste vyriešiť, ak by ste vedeli presné poradie študentov? Viete dynamickým programovaním vypočítať PotrebnyCas[student][uloha] ? Kto mohol riešiť predchádzajúce úlohy?
  • Stačí teda len vyskúšať všetky možné permutácie poradia študentov (tých nie je veľa - 6) a vybrať tú najlepšiu.

V jazyku Python môťete použiť itertools.permutation.

V jazyku C++ je v STL knižnici funkcia next_permutation.

5 akceptovaných riešení za plný počet bodov

  • 0.65-0.90 (Java)

Riešenie je teda v $\Theta(6.n)=\Theta(n)$

In [1]:
from itertools import permutations
print(*permutations((1, 2, 3))) #vypíše všetky permutácie, samotná metóda vráti generátor/iterátor (preto je na začiatku *)
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)

Min

4 body do 31.03.2020 10:00
2 body do 07.04.2020 10:00

Toto je úloha na intervalový strom, vytvorte vlastnú implementáciu.