Solução escrita por João Pedro Castro
Conhecimento prévio necessário:
Primeiro vamos tentar achar uma maneira de conferir se para um $$k$$ fixo conseguimos ou não coletar os $$c$$ pokédolares. Uma solução para essa tarefa é simplesmente ordenar o vetor $$a$$ (guarda quantidade de pokédolares recebidos ao capturar um pokéamigo) de forma decrescente, e 0-indexado, para então no i-ésimo dia capturar o pokéamigo equivalente a posição $$i~mod~k$$ do vetor ordenado (se essa posição for válida), indo de $$i=0 \rightarrow i=d-1$$.
É fácil de entender por que isso funciona, já que ordenando o vetor de forma decrescente você sempre vai usar os de maior valor primeiro, o que garante que a quantidade deles a serem capturados é sempre $$\geq$$ do que dos outros. De forma exemplificada, o que estamos fazendo é indo da posição $$0 \rightarrow k-1$$ repetidas vezes até os $$d$$ dias passarem, portanto, escolha a forma de implementar que você preferir. Note que dessa forma o $$k$$ não tem a mesma definição do enunciado, pois deveríamos seguir mais um dia até voltar para o primeiro (por exemplo, fazemos $${0, 1}$$ ao invés de $${0, 1, 2}$$ com $$k = 2$$), para corrigir isso é só usar $$k – 1$$ ao imprimir a resposta.
Agora, para achar o $$k$$ correto devemos executar uma busca binária tentando encontrar o maior valor aceito possível, com os limites sendo $$0$$ e $$d+2$$. O motivo do $$d+2$$ é que se o $$k$$ pode ser maior que o próprio $$d$$, ele pode ir até o infinito, já que ele vai somar as mesmas $$d$$ posições toda vez, e elas vão ser sempre maiores que $$c$$. Agora, se o ponteiro da esquerda/direita (eles coincidem no final) acabar em $$0$$, isso significa que é impossível, pois nem o $$k = 1$$ funcionou.