Da li neko zna da mi da smernice za algoritam? Hvala
1 Like
Posto su vestine vojnika (vrednosti u nizovima) prilicno male, za svaku ukupnu moc mozemo izracunati broj nacina na koji ju je moguce napraviti. Nazovimo W_k(x) broj nacina da se napravi suma x, koristeci po jedan broj iz prvih k nizova.
Ako koristimo samo prvi niz, resenje je ocito W_1(x) = \text{broj pojavljivanja } x \text{ u prvom nizu} .
Ako koristimo prvih k nizova, svaka kombinacija ukupne sume x se sastoji od nekog elementa a_{k,i} iz k-tog niza i sume x - a_{k,i} iz prvih k-1 nizova. Dakle, ako “probamo” sve moguce elemente i za svaku sumu i saberemo broj nacina da se dobiju sume u prvih k-1 nizova, dobijamo:
W_k(x) = \sum_{i=1}^n W_{k-1}(x - a_{k,i})
(ako a_{k,i} > x smatramo da je ta vrednost 0).
Nakon sto ovo izracunamo, niz W_n je kompletan opis sortiranog niza ukupnih moci (za svaku znamo koliko se puta pojavljuje) i iz njega lako mozemo rekonstruisati resenje.
Napomena za implementaciju: vrednosti u W mogu biti prilicno velike, tako da treba biti pazljiv da ne dodje do overflow-a. Posto znamo da k < 10^{18}, mozemo ograniciti vrednosti na ovu granicu (ako W_k(x) > 10^{18}, mozemo ga postaviti na 10^{18} i resenje se nece promeniti) posle svakog sabiranja i time resiti problem overflow-a.
2 Likes