Solução escrita por João Pedro Castro
Conhecimento prévio necessário:
Podemos perceber que só precisamos considerar a compra de um pacote $$i$$ se não existe nenhum outro pacote $$j$$ tal que $$i < j$$ e $$c_i \leq c_j$$, já que sempre será mais vantajoso comprar o pacote $$j$$, que tem mais doces e é mais barato (ou tem o mesmo preço); vamos guardar os pacotes que são considerados do menor para o maior em um array $$s$$. Agora, podemos usar a ideia gulosa de comprar a quantidade máxima possível de um pacote $$s_i$$ para $$1 \leq i \leq |s|$$, e depois usando o resto de $$c_{s_i}$$ pela quantidade restante de moedas $$k$$ para comprar o próximo pacote $$s_{i+1}$$; e como comprar o próximo pacote $$x$$ vezes é melhor do que comprar o pacote atual $$x$$ vezes, podemos simplesmente usar a expressão a seguir para descobrir quanto iremos comprar do pacote $$s_i$$:
$$\lfloor \frac{k}{c_{s_i}} \rfloor – min(\lfloor \frac{k}{c_{s_i}} \rfloor, \lfloor \frac{k~mod~c_{s_i}}{c_{s_{i+1}} – c_{s_i}} \rfloor)$$
E então usar soma de prefixo para escrever o maior array lexicograficamente possível.