Solução Informática - Nível Iniciante - Semana 40

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.

Clique aqui para conferir o códgio