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)$$.

https://gist.github.com/luciocf/5e5c7ebaaf7b9f5ffeef632c5df10590

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)$$.

https://gist.github.com/luciocf/e56c09f6b71f352ab2cbe9317d97720f

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)$$.

https://gist.github.com/luciocf/3c42c53aafed19130a7696f77032db19

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)$$.

https://gist.github.com/luciocf/2318255635bfa48817b48a4dab6bc4d8