Bolinha Quicante

Solução escrita por Malu Azevedo

Conhecimentos necessários:

• Começando do zero
• Ordenação

O problema consiste em determinar a maior pontuação possível ao arremessar uma bolinha com um pulo fixo $B$, escolhendo estrategicamente a posição inicial $X$ de forma que a bolinha colete o máximo de moedas em sua trajetória infinita pelas posições $X, X + B, X + 2B, \dots$.

Ideia Central

O problema consiste em determinar a maior pontuação acumulada ao arremessar uma bolinha com um salto fixo $B$, aproveitando o fato de que todas as posições visitadas a partir de uma coordenada inicial compartilham o mesmo resto na divisão por $B$. Para agrupar todas as moedas que pertencem à mesma trilha de pulos, podemos associar a cada moeda o par formado pelo resto da sua posição dividida por $B$ e pela sua pontuação. Ao ordenar essas duplas, todas as moedas com o mesmo resto ficam agrupadas consecutivamente, permitindo somar suas pontuações de forma simples e linear para encontrar a trilha de maior valor.

Abordagem completa

Lemos os valores de $N$ e $B$, e em seguida preenchemos os vetores de posições e pontuações. Criamos um vetor de pares (pair<int, int>) onde o primeiro elemento armazena o resto da posição da moeda dividida por $B$ (x[i] % b) e o segundo armazena a pontuação (p[i]). Em seguida, ordenamos esse vetor de pares usando a função sort, o que garante que moedas com o mesmo resto fiquem juntas. Percorremos o vetor ordenado acumulando a pontuação das moedas com o mesmo resto em soma_atual e atualizando a resposta máxima sempre que mudamos de resto. Ao final, garantimos a verificação do último grupo e imprimimos a maior pontuação encontrada. A complexidade de tempo é $O(N \log N)$ devido à ordenação.

Clique aqui para ver o código completo.