Solução Informática - Nível Avançado - Semana 33

Solução escrita por Enzo Dantas

Conhecimento prévio recomendado:

• Introdução a DP

A observação essencial é que $N, K \le 8$. Isso implica que é possível brutar todas as possíveis distribuições, e faremos isso usando o seguinte método: cada pacote de cookie será assinalado a uma pessoa. Lembrando que $N$ é a quantidade de pacotes e $K$ é a quantidade de crianças, imagine um array $arr$ de tamanho $N$ tal que cada posição tem um valor de 1 a $K$, indicando que o pacote da posição $i$ foi pego pela criança $arr_i$. {2, 1, 2, 4, 3}, por exemplo, indica que os pacotes 1 e 3 estão com a criança 2, o pacote 5 está com a criança 3, e assim por diante. Para testar todas as possíveis distribuições, olhamos de posição em posição e testamos colocar cada valor entre 1 e $K$ na posição atual usando recursão.

Como cada posição pode ter um valor entre 1 e $K$ e temos $N$ posições, a complexidade final é $O(K \cdot K \cdot ... \cdot K) = O(K^N)$.

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.