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: