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:
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.
Cartomância
Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
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
Espelhos
Comentário escrito por João Pedro Castro
Conhecimentos Prévios Necessários:
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:
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.