OBOI 2024 - Fase 1 - Nível Pleno

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos os nossos materiais.

Pedras

Escrito por Murilo Maeda Kataoka

Conhecimento prévio necessário:

• Estruturas Condicionais

Perceba que, devido à alta quantidade de pedras que podem estar na pilha, não é possível, para a solução completa, simplesmente simular as jogadas. Dessa forma, é necessária a observação de que, quando o número de pedras ,$N$, tem resto:

• 0 na divisão por 3: Lalic ganha.
• 1 na divisão por 3: Lalic ganha
• 2 na divisão por 3: Enzo ganha

A partir disso, basta checar qual o resto de $N$ na divisão por 3 e imprimir o resultado correto.

Clique aqui para ver o código

Cartomância

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Strings

A ideia vai ser manter quatro variáveis auxiliares $la, ra, lb, rb$, onde $la, ra$ vai ser a menor e a maior pontuação possível do Lobo e $lb, rb$ a menor e a maior pontuação possível do Enzo. Além disso, mantenha mais uma variável booleana $empate$, que mantém se o jogo é um empate ou não (Só vamos alterar ela caso, em algum momento, a pontuação do Enzo e do Lobo aumentem de maneiras distintas). Vamos fazer um for para percorrer todas as letras da string. Na i-ésima interação do for, vamos chegar os casos referente a i-ésima letra:

• Se $a[i] == b[i]$ e $a[i] \neq ?$, portanto, a pontuação de Lobo e de Enzo aumentam da mesma maneira, logo, temos 2 casos
  • Se $g[i] == ?$, então, a resposta de Lobo e de Enzo podem aumentar ou não, mas elas vão aumentar juntas, ou seja, não alteramos a variável empate, e aumentamos ambas as respostas máximas ($ra$ e $rb$) em $1$.
  • Caso contrário,
    • Se $a[i] == g[i]$, aumente $la, ra, lb, rb$ em $1$.
    • Caso contrário, faça nada.
• Caso contrário, se $g[i] == ?$, veja que agora, as pontuações de Lobo e de enzo podem crescer de maneiras distintas, ou seja, pode acontecer de a pontuação de Lobo aumentar e Enzo não, e vice versa. Portanto, alteramos a variável empate para falso, e aumentamos a resposta máxima de Lobo e de Enzo ($ra, rb$) em $1$, pois ambas as pontuações deles podem aumentar.
• Caso contrário
  • Se $a[i] == ?$, com o mesmo raciocínio acima, alteramos a variável empate para falso, e aumentamos $ra$ em $1$
  • Caso contrário, aumente $la$ e $ra$ caso $a[i] == g[i]$.
• E faça esse mesmo if para a string $b$:
  • Se $b[i] == ?$, com o mesmo raciocínio acima, alteramos a variável empate para falso, e aumentamos $rb$ em $1$
  • Caso contrário, aumente $lb$ e $rb$ caso $b[i] == g[i]$.

Pronto, lidamos com todos os casos! Agora, basta ver o resultado de cada variável e ver o que ele nos entrega:

• Caso $la > rb$, ou seja, a menor resposta possível de Lobo é maior que a maior resposta possível de Enzo, logo, Lobo sempre ganha
• Caso contrário $lb > ra$, pelo mesmo argumento, Enzo sempre ganha de Lobo
• Caso contraŕio, verifiquemos a variável empate
  • Caso empate seja verdadeiro, imprima empate
  • Caso contrário, imprima indefinido

Clique aqui para ver o código

Espelhos

Comentário escrito por João Pedro Castro

Conhecimentos Prévios Necessários:

• Soma de Prefixo

As primeiras três parciais se resumem à trocar manualmente os dígitos pela sua versão "espelhada". O único conhecimento necessário fora de loops/vetores é o da regra de divisibilidade do 3: a soma dos algarismos na forma decimal ser divisível por 3 implica que o número é divisível por 3, e o contrário também é válido. Isso vem do fato que $10^n \equiv 1~(mod~3)$.

A solução completa vem de uma observação da operação de espelho: ela não tem nenhum efeito na divisibilidade por 3 de qualquer intervalo. E a razão é muito simples, perceba que: $0-0 \equiv 1-1 \equiv 8-8 \equiv 2 - 5 \equiv 6 - 9 \equiv 0~(mod~3)$. E como individualmente, para um único dígito, não existe diferença no resto da divisão por 3, para a soma de vários dígitos também não existirá qualquer diferença.

Por fim, só é necessário realizar uma soma de prefixo para pode calcular a soma de todos os dígitos de um intervalo em $O(1)$. A complexidade final é $O(N+Q)$.

Clique aqui para conferir o código

Xadrez

Comentário por Fernando Gonçalves

Conhecimento prévio necessário:

• Backtracking

Primeiro, precisamos entender como testar se reis se atacam.

Sabemos que um rei pode se mover para qualquer posição em que a maior diferença de coordenadas é no máximo $K$, portanto um rei está atacando outro quando a maior diferença de coordenada é menor ou igual $K$.

Por exemplo, para $K = 3$, os reis nas posições $(3, 5)$ e $(1, 8)$ se atacam, pois $max(2, 3) = 3 \leq 3$.

Outra observação é que o máximo de reis que é possível colocar no tabuleiro dadas as condições do problema é 9 reis. Assim, o problema se resume a achar os arranjos em que $N \leq 9$, pois todo $N$ maior terá resposta igual a $0$.

Com isso, podemos testar todos os arranjos dos reis com uma backtrack. Como muitos casos são inválidos, esse algoritmo com algumas podas é suficiente para resolver o problema.

Clique aqui para conferir o código