Úloha má to isté zadanie ako úloha Vojaci
Rotu tvorí $n$ vojakov. Chceme z nich vybrať $k$-člennú hliadku. Práve jeden člen hliadky bude jej veliteľom.
Každého vojaka vieme popísať postupnosťou $d$ nezáporných celých čísel. (Tie predstavujú jeho vlastnosti: napr. nakoľko neznáša Justina Biebera, z ktorej strany otvára banán a podobne. Napr. pre $d=3$ môžeme mať vojaka $(0,3,1)$ a iného vojaka $(4,7,1)$.)
Kompatibilita dvoch vojakov $A=(a_1,\dots,a_d)$ a $B=(b_1,\dots,b_d)$ je rovná číslu $a_1b_1 + \cdots + a_db_d$. (Napríklad kompatibilita vojakov z predchádzajúceho odseku je $0\cdot 4 + 3\cdot 7 + 1\cdot 1 = 22$.)
Kompatibilita hliadky je súčet kompatibilít dvojíc vojakov, ktorí ju tvoria, pričom dvojice obsahujúce veliteľa hliadky rátame s váhou 3. (Teda ak by jeden z našich dvoch vojakov bol veliteľom hliadky, ku kompatibilite hliadky by sme za nich dvoch pripočítali $3\cdot 22 = 66$.)
Vašou úlohou je napísať program, ktorý pre danú rotu vyberie hliadku s najväčšou možnou kompatibilitou.
Tentokrát máme iné obmedzenia. Platia nasledovné nerovnosti: Platí $1\leq k\leq n\leq \mathbf{1000}$, $1\leq d\leq 10$ a pribudla nová podmienka navyše: ${n \choose k} \cdot (n+k^3 d) \leq 10\,000\,000$.
Tretia, odstrašujúco pôsobiaca nerovnosť, nám hovorí nasledovné: Ak vygenerujeme všetkých ${n\choose k}$ možných $k$-členných hliadok, pre každú vyskúšame všetkých $k$ možných veliteľov, a zakaždým hrubou silou spočítame jej kompatibilitu, spravíme nanajvýš 10 miliónov logických krokov (čo je málo).
Rozmyslite si ale, že už si nemôžeme dovoliť vygenerovať všetkých $2^n$ podmnožín vojakov, lebo $2^{1000}$ je strašne veľa. Musíme teda nejako vygenerovať len všetky $k$-prvkové podmnožiny a žiadne iné.
Dobrá rada: Existuje funkcia next_permutation. Zistite si, ako sa používa a čo robí.
Potom si zistite, čo sa stane, ak ju dokola spúšťate na poli, ktoré obsahuje nasledovné hodnoty:
$(0,0,0,0,1,1,1)$. Ako vám to pomôže vyriešiť úlohu?
Bonus: Nechce sa vám písať for-cyklus na výber veliteľa? Skúste namiesto toho vymyslieť trik, ako
výber veliteľa spraviť priamo počas výberu konkrétnej podmnožiny pomocou next_permutation.
... sú opäť všetky rovnaké ako v úlohe vojaci.
(Ale nezabudnite tentokrát na uloženie kompatibility hliadky použiť dostatočne veľkú premennú!)