OBI 2021 – Fase 2 Turno A – Programação Nível Júnior
Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!
Comentário escrito por Pedro Racchetti, Anita Almeida, Luca Dantas e Thiago Mota
Para conferir a prova na íntegra, clique aqui.
Duplas de Tênis
Conhecimento prévio necessário:
Primeiro, para simplificar a solução, chamaremos os jogadores de $$A$$, $$B$$, $$C$$ e $$D$$. Para este problema, nota-se que só temos 3 configurações possíveis de duplas:
- $$(A,B)$$ e $$(C,D)$$;
- $$(A,C)$$ e $$(B,D)$$;
- $$(A,D)$$ e $$(B,C)$$.
Portanto, basta testar a diferença dos valores para cada configuração, e imprimir a menor delas.
A complexidade da solução é $$O(1)$$. Segue o código, comentado, para melhor compreensão:
Pangrama
Conhecimento prévio necessário:
Para esse problema, começamos percorrendo o vetor de letras (que corresponde à frase lida na entrada) com a estrutura de repetição $$for$$, e marcamos como $$1$$ o índice de cada letra na primeira vez em que ela aparece. Durante esse loop, também verificamos se o caractere sendo visto é a primeira aparição da letra; se sim, adicionaremos $$1$$ à quantidade de letras diferentes lidas ao final.
Cabe destacar alguns detalhes, como a transformação de uma letra em seu identificador, de acordo com a tabela ASCII, em que subtraímos da letra lida o valor de ‘$$a$$’ para obtermos $$a=0$$, $$b=1$$, $$c=2$$ e etc. Além disso, precisamos verificar se a letra lida realmente é uma letra (identificador $$\geq 0$$) e realizar uma verificação final para checar se foram identificadas 23 letras diferentes.
A complexidade da solução é $$O(|C|)$$. Segue o código para melhor compreensão da solução:
Robô
Conhecimento prévio necessário:
Neste problema, precisamos apenas simular a ação do robô, adicionando um valor à resposta a cada vez que ele passar pela estação desejada.
Para simular o movimento, basta andarmos na direção que a entrada do problema nos indica (1 anda para a direita, -1 anda para esquerda). Para manter a propriedade circular, podemos utilizar uma de duas técnicas: na primeira, utilizaremos um if para checar se uma posição é menor que $$1$$ ou maior que $$n$$, e assim atribuí-la para o valor correto do outro lado do círculo (se for $$0$$ vira $$n$$, se for $$n+1$$ vira $$1$$). A outra possibilidade é salvar os valores $$0$$-indexados (de $$0$$ a $$n-1$$) e utilizar o operador de módulo para atribuir o valor correto.
A complexidade da solução é $$O(C)$$. Para melhor entendimento, confira os códigos abaixo, que implementam as duas maneiras de resolver o problema, mencionadas acima:
Solução 1, utilizando if
Solução 2, utilizando módulo
Média e Mediana
Conhecimento prévio necessário:
Para que a média seja igual a mediana, basta que a distância do elemento do meio para as pontas seja a mesma, por exemplo: $$2$$ $$5$$ $$7$$, a distância do $$5$$ para as pontas é a mesma, logo a média e a mediana ficam no mesmo ponto. Podemos demonstrar isso matematicamente:
Pegue 3 números em ordem não-decrescente $$a, b, c$$, onde $$b$$ é a mediana. Para que a média seja igual a mediana precisamos é necessário que $$\frac{a+b+c}{3} = b$$. Logo podemos abrir a conta e chegar na conclusão apresentada acima.
$$ \frac{a+b+c}{3} = b $$
$$ a+b+c = 3b $$
$$ ac = 2b $$
$$ c-b = b-a $$
Para resolver o problema, basta escolher qualquer número de tal forma que a diferença entre o maior e o menor seja igual o do meio. Segue o código: