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:

	#include<bits/stdc++.h>
	using namespace std;

	int a, b, c, d;


	int main(){
	//Primeiro, lemos a entrada
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	scanf("%d", &d);

	//Então, testamos cada configuração possível.
	int ans = abs((a+b)-(c+d));
	ans = min(ans, abs((a+c) - (b+d)));
	ans = min(ans, abs((a+d) - (b+c)));
	printf("%d\n", ans);
	}

view raw duplas.cpp hosted with

by GitHub

Retângulo

Conhecimento prévio necessário:

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!

	// Comentário NOIC - OBI Fase 2 P1/P2 - Retângulo
	// Complexidade: O(N log N)
	// Escrito por Lúcio Figueiredo

	#include <bits/stdc++.h>

	using namespace std;

	typedef long long ll;

	const int maxn = 1e5+10;

	int L[maxn];
	ll P[maxn]; // soma de prefixo
	int D[maxn];

	ll S(int i, int j)
	{
	return P[j] - P[i];
	}

	int main(void)
	{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
	scanf("%d", &L[i]);

	P[i] = P[i-1] + 1ll*L[i]; // calculamos as somas de prefixo
	}

	for (int i = 1; i <= n; i++)
	{
	// busca binária para encontrar D[i]

	int ini = i+1, fim = n, ans = -1;

	while (ini <= fim)
	{
	int mid = (ini+fim)>>1;

	if (2*S(i, mid) == S(0, n)) // se é um diâmetro
	{
	ans = mid;
	break;
	}

	if (S(i, mid) > S(0, n)/2) fim = mid-1;
	else ini = mid+1;

	}

	D[i] = ans;
	}

	// quantidade de pontos com D[i] != -1
	int qtd = 0;
	for (int i = 1; i <= n; i++)
	if (D[i] != -1)
	qtd++;

	if (qtd >= 2) printf("S\n");
	else printf("N\n");
	}

view raw retangulo.cpp hosted with

by GitHub

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

	#include <cstdio>

	int main() {
	int n, c, s; scanf("%d %d %d", &n, &c, &s);
	int ans = 0, pos = 1;
	if(s == 1) ++ans;
	for(int i = 0; i < c; i++) {
	int v; scanf("%d", &v);
	pos += v;
	if(pos == 0) pos = n;
	if(pos == n+1) pos = 1;
	if(pos == s) ++ans;
	}
	printf("%d\n", ans);
	}

view raw robo1.cpp hosted with

by GitHub

Solução 2, utilizando módulo

	#include <cstdio>

	int main() {
	int n, c, s; scanf("%d %d %d", &n, &c, &s);
	int ans = 0, pos = 0;
	--s; // 0-indexamos
	if(s == 0) ++ans;
	for(int i = 0; i < c; i++) {
	int v; scanf("%d", &v);
	pos = (pos + v + n) % n;
	if(pos == s) ++ans;
	}
	printf("%d\n", ans);
	}

view raw robo2.cpp hosted with

by GitHub

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:

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:

	#include <bits/stdc++.h>

	using namespace std;

	int main() {
	int a, b;
	cin >> a >> b;
	if (a > b)
	swap(a, b); // 'a' vira o menor elemento

	// Vamos fazer o elemento 'a' ser a mediana.
	int c = a - (b - a); // c < a < b

	cout << c << '\n';
	return 0;
	}

view raw media.cpp hosted with

by GitHub