OBI 2021 - Fase 2 Turno A - Programação Nível 1

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, Lúcio Figueiredo, Luca Dantas e Thiago Mota

Para conferir a prova na íntegra, clique aqui.

Duplas de Tênis

Conhecimento prévio necessário:

• Entrada, saída e programação básica

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:

Retângulo

Conhecimento prévio necessário:

• Somas de prefixo
• Busca Binária

Para resolver o problema, vamos utilizar a seguinte observação:

Observação: Um quadrilátero $ABCD$ demarcado em um círculo é um retângulo se e somente se as diagonais $AC$ e $BD$ são diâmetros do círculo.

Com esta observação, basta sabermos se existem quatro pontos $A < B < C < D$ no círculo tais que os segmentos $AC$ e $BD$ são diâmetros, ou seja, a soma dos arcos de $A$ a $C$ e a soma dos arcos de $B$ a $D$ ambas valem metade da circunferência do círculo.

Defina $S(i, j)$ como a soma dos arcos entre os pontos $i$ e $j$ $(i < j)$, ou seja, $L_{i+1} + L_{i+2} + ... + L_j$. Além disso, defina $D(i)$ como o ponto $j$ tal que o segmento $ij$ é um diâmetro, ou $-1$ caso não exista. Vamos computar, para cada ponto $i$, o seu valor $D(i)$. Pela definição de diâmetro, teremos que $ij$ é um diâmetro se e somente se $S(i, j)$ vale metade da circunferência, ou seja, $\frac{S(0, n)}{2}$. Portanto, para encontrar o ponto $j$ (se existir), podemos utilizar uma busca binária no intervalo $[i+1, n]$. Para calcularmos os valores $S(i, j)$ de forma eficiente, basta precalcularmos a soma de prefixo do vetor $L$; assim, se $P_x$ é a soma do $x$-ésimo prefixo, conseguimos calcular $S(i, j)$ em $O(1)$, já que $S(i, j) = P_{j} - P_{i-1}$.

Após computarmos os valores $D(i)$, resta apenas checar se existem dois pontos $A$ e $B$ tais que $D(A) \neq -1$ e $D(B) \neq -1$. Se sim, existe um retângulo demarcado no círculo formado por $A, B, D(A)$ e $D(B)$. Senão, não existe retângulo algum.

Já que realizamos uma busca binária para cada um dos $N$ pontos, a complexidade da solução é $O(N \cdot \log_{} N)$. Confira o código abaixo para melhor entendimento:

PS.: Existe uma solução com complexidade $O(N)$, utilizando a técnica de Two Pointers para encontrar os valores $D(i)$. Como exercício, tente implementar esta solução!

Robô

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops

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:

• Programação Básica: Variáveis

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:

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: