Comentário Noic OBI 2019 - Fase 1 - Programação Nível 1

Comentário por Lúcio Cardoso

Para conferir a prova na íntegra, clique aqui.

Idade de Dona Mônica

Conhecimento prévio necessário:

Entrada e Saída

Seja $C$ a idade do terceiro filho. Note que $A+B+C = M$ , e logo, $C = M-A-B$ . Assim, o nosso programa deve imprimir o máximo dentre $A, B$ e $M-A-B$ . Para isso, utilizaremos a função max() do C++.

Complexidade: $O(1)$ .

	// Comentário Noic OBI 2019 - Fase 1 - Programação Nível 1
	// Idade de Dona Mônica

	#include <bits/stdc++.h>

	using namespace std;

	int main(void)
	{
	int m, a, b;

	cin >> m >> a >> b;

	int c = m-a-b;

	// maximo dentre a, b, e c
	cout << max(a, max(b, c)) << "\n";
	}

view raw

comentario-noic-f1-p1-idade.cpp

hosted with ❤ by GitHub

Nota Cortada

Conhecimento Prévio Necessário:

Estruturas Condicionais
Área do Trapézio

Perceba que os dois pedaços resultantes do corte terão o formato de um trapézio. Assim, lembrando que a área de um trápezio de altura $h$ e bases $a, b$ é $\frac{h \cdot (a+b)}{2}$ , teremos que a área da figura mais à esquerda será igual a $\frac{70 \cdot (B+T)}{2}$ . Tendo isso em mente, podemos agora simplesmente checar se a área resultante é maior, igual ou menor que metade da área do retângulo, imprimindo, assim, as respectivas respostas.

Complexidade: $O(1)$ .

	// Comentário Noic OBI 2019 - Fase 1 - Programação Nível 1
	// Nota Cortada

	#include <bits/stdc++.h>

	using namespace std;

	int main(void)
	{
	int B, T;

	cin >> B >> T;

	// metade da área do retângulo
	int metade = (70*160)/2;

	// área do lado esquerdo
	int area = (70*(B+T))/2;

	if (area == metade) cout << "0\n";
	else if (area > metade) cout << "1\n";
	else cout << "2\n";
	}

view raw

comentario-noic-f1-p1-nota.cpp

hosted with ❤ by GitHub

Jogo de Dominós

Conhecimento prévio necessário:

Entrada e Saída
Matemática Básica

Fato 1: O valor da soma $1 + 2 + 3 + ... + N$ , para um $N$ inteiro, é igual a $\frac{N \cdot (N+1)}{2}$ .

Seja $T(x)$ a quantidade de peças em que um lados tem valor $x$ e o outro lado possui um valor menor ou igual a $x$ . É fácil notar que o total de peças em um jogo duplo- $N$ será igual a $T(0) + T(1) + T(2) + ... + T(N)$ . Além disso, podemos notar que $T(x) = x+1$ , já que a quantidade de valores não-negativos menores ou iguais a $x$ é $x+1$ . Assim, a resposta do nosso problema é $1 + 2 + 3 + ... + (N+1)$ , e pelo Fato 1, sabemos que esta soma possui valor igual a $\frac{(N+1) \cdot (N+2)}{2}$ .

Note que o Fato 1 não era necessário para resolver o problema: Poderíamos resolvê-lo usando simplesmente um loop que soma os valores de $1$ a $N+1$ em uma variável que guarda a resposta, com complexidade $O(n)$ .

Complexidade: $O(1)$ ou $O(n)$ .

	// Comentário Noic OBI 2019 - Fase 1 - Programação Nível 1
	// Jogo de Dominós

	#include <bits/stdc++.h>

	using namespace std;

	int main(void)
	{
	int n;

	cin >> n;

	// 1 + 2 + ... + (N+1)
	cout << ((n+1)*(n+2))/2 << "\n";
	}

view raw

comentario-noic-f1-p1-jogo.cpp

hosted with ❤ by GitHub

Distância entre amigos

Conhecimento prévio necessário:

Estruturas de Repetição

Seja $H(i)$ a quantidade de andares no $i$ -ésimo prédio. Pela descrição do problema, temos que a distância entre dois apartamentos $i$ e $j$ (com $j > i$ ) é igual a $H(i) + H(j) + (j-i)$ . Vamos, então, descobrir para cada prédio $j$ ( $1 \leq j \leq N$ ) a maior distância distância possível para algum prédio com índice menor que $j$ . Pela expressão obtida anteriormente, é fácil notar que o prédio $i$ que dará a maior distância para o prédio $j$ é aquele com valor $H(i)-i$ máximo, já que $H(j)$ e $j$ são valores que independem da escolha de $i$ .

Logo, podemos iterar por cada prédio de $1$ a $N$ , e, ao mesmo tempo, usar uma variável $maior$ que guarda o maior valor $H(i)-i$ encontrado até a iteração atual. Assim, a resposta do problema será o valor máximo de $H(j) + j + maior$ , para $j = 1, 2, ..., N$ .

Complexidade: $O(N)$ .

	// Comentário Noic OBI 2019 - Fase 1 - Programação Nível 1
	// Distância entre amigos

	#include <bits/stdc++.h>

	// valor "infinito"
	const int inf = 1e9+10;

	using namespace std;

	int main(void)
	{
	int n;
	cin >> n;

	// inicialmente, maior começa com um valor menor que
	// o mínimo valor possível
	int maior = -inf;

	// resposta do problema
	int ans = -inf;

	for (int i = 1; i <= n; i++)
	{
	// altura do i-ésimo prédio
	int h;
	cin >> h;

	// atualizamos a resposta
	ans = max(ans, h+i+maior);

	// atualizamos o maior valor (H(i)-i)
	maior = max(maior, h-i);
	}

	cout << ans << "\n";
	}

view raw

comentario-noic-f1-p1-amigos.cpp

hosted with ❤ by GitHub