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.
Platí $1\leq k\leq n\leq 15$ a $1\leq d\leq 10$. Vojakov je teda nanajvýš 15 a vlastností je nanajvýš 10. To znamená, že si môžete dovoliť nasledovné riešenie: vygenerovať všetky možné podmnožiny vojakov, vybrať spomedzi nich tie správne veľké, zakaždým vyskúšať všetky možné výbery veliteľa a pre každú hliadku s veliteľom vypočítať jej kompatibilitu.
Dobrá rada: Pozrime sa na všetky $n$-bitové čísla -- teda čísla od 0 po $2^n - 1$.
Každému z nich vieme priradiť jednu z $2^n$ podmnožín vojakov (ako?).
Pomôcť vám pri implementácii môžu bitové operácie. Napríklad (x & 1<<y) je test,
či má číslo $x$ nastavený bit $y$.
V prvom riadku sú čísla $n$, $k$ a $d$.
Nasleduje $n$ riadkov, v každom z nich je popis jedného vojaka: $d$ celých čísel (z rozsahu od 0 do 1000).
Vypíšte jeden riadok a v ňom najväčšiu možnú kompatibilitu hliadky.
5 2 2
1 8
6 3
7 0
9 7
5 6
261
Najlepšie je vybrať do hliadky štvrtého a piateho vojaka. Je jedno, kto z nich bude veliteľom, kompatibilita hliadky bude tak či tak $3\cdot (9\cdot 5 + 7\cdot 6)$.
4 1 7
9 1 2 5 1 5 3
2 0 0 1 5 1 4
2 8 1 5 7 3 9
7 0 0 6 6 5 9
0
Veliteľom (a zároveň jediným členom) hliadky môže byť ktokoľvek -- keďže v hliadke nemáme žiadnu dvojicu vojakov, kompatibilita hliadky je vždy 0.
6 3 4
4 5 4 7
7 5 9 6
8 0 5 8
3 5 2 2
2 6 3 9
1 8 7 1
948
Najlepším riešením je hliadka tvorená prvými troma vojakmi, pričom druhý bude veliteľom.