OBOI 2023 - Fase 1 - Nível Pleno

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.

Para conferir a prova na íntegra, clique aqui.

Gohan

Comentário escrito por Murilo Maeda

A resolução é bem simples: basta comparar a soma das notas. Já que ambas as somas são divididas pelo mesmo valor, se a soma de um é maior que a do outro, a média também será.  O problema é que os valores de média podem ir até $10^{15}$, que é maior do que o limite do int. Para resolver isso, basta mudar para long long int. Note também que se você quiser comparar as médias (fazendo a divisão), é necessário usar long double, já que apenas com double a divisão retorna um número com casas o suficiente para o código retornar que as duas médias são iguais, mesmo que elas sejam diferentes.

Clique aqui para conferir o código

Matriz Maluca

Comentário escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Matrizes

Vamos criar duas variáveis, $Lobo$ e $Enzo$. Em cada jogada, nos é dado dois valores $(i, j)$, então, adicionamos os números que estão na linha $i$ e os valores que estão na coluna $j$, sem repetir o valor de $(i,j)$, para a variável Lobo, se for a jogada do lobo, ou para a variável Enzo, se for a vez do enzo, e então, trocamos o valor de cada um desses números que adicionamos por 0.

Depois de todas as operações, vemos se Enzo é maior que Lobo: Se sim, imprimimos Enzo. Se Enzo = Lobo, então imprimos empate, e caso nenhum dos anteriores aconteça, imprimimos Lobo.

Clique aqui para conferir o código

Forte Demais

Comentário escrito por João Pedro Castro

Conhecimento prévio necessário:

• Two pointers

Sendo impossível adicionar novas anilhas em qualquer um dos lados, a estratégia ideal é a de simplesmente remover a anilha que está na extremidade do lado mais pesado (o lado com maior $\text{soma total do lado} - \text{quantidade removida do lado}$) até que os dois lados tenham o mesmo peso.

Um cenário que sempre vai acontecer, pois no pior dos casos é necessário remover todas as anilhas e deixar ambos os lados com peso 0. Isso pode ser feito facilmente usando dois pointeiros: guardando a soma total de cada um dos lados, e a soma das anilhas removidas até agora em cada um dos lados.

É importante ressaltar que a soma total de um dos lados pode passar do limite de um $int$ de 32 bits, por isso é necessário usar o tipo $long~long$ no C++.

Clique aqui para conferir o código

Medalhas

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• Algoritmo Guloso

Simplificaremos o enunciado para o seguinte: Dados dois conjuntos de inteiros distintos, diga a quantidade mínima de números que devem ser retirados para que o maior e o segundo maior número estejam em conjuntos distintos.

Primeiramente, precisamos achar o maior e o segundo maior. Isso pode ser feito colocando todos os números em um array $V$, ordenando-o em ordem decrescente e pegando os dois primeiros. Caso já estejam em conjuntos distintos, não é preciso realizar nenhuma operação e a resposta é 0. Caso contrário, o maior e o segundo maior estão no mesmo conjunto. Aqui podemos realizar a seguinte ideia repetidamente: retirar o 2o maior e checar se o 3o maior está no outro conjunto. Caso contrário, retirar o 3o e checar se o 4o está no outro conjunto. Caso contrário, (...). Eventualmente (possivelmente após retirar todos do conjunto exceto o maior) o maior estará em um conjunto e o 2o maior estará em outro.

Assuma que o maior e o 2o maior estão no mesmo conjunto. Note que retirar números que não são o maior ou o 2o maior não muda o fato de que os dois maiores estão na mesma pilha. Logo, independentemente dos números específicos que devem ser retirados, um desses dois obrigatoriamente será retirado e é possível retirá-los antes das outras operações.

Além disso, note que tanto faz retirar o maior ou o 2o maior. O que não foi retirado será o maior de todos e chegaremos na mesma ordem relativa. Portanto, o algoritmo acima realiza o número mínimo de operações.

Código