Comentário NOIC OBI 2021 - Fase 2 Turno A - Programação Nível Júnior

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:

Demonstração

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

[collapse]

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: