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:

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:

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:

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:

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