Úloha má to isté zadanie ako úloha Vojaci
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ú!)