Simulado - Segunda Fase OBI 2021 - Comentário PJ

Comentário por Lúcio Figueiredo, Pedro Racchetti e Anita Almeida

Para conferir a prova na íntegra, clique aqui.

Operações

Conhecimento Prévio Necessário:

• Vetores

Inicialmente, observe que se fizermos uma operação que remove alguns números de valor $v$, não é ótimo realizar outra operação que remove números de mesmo valor, já que estes poderiam ser incuídos na primeira operação. Logo, em uma solução ótima, cada operação realizada remove números com valores distintos entre si. Portanto, podemos concluir que a resposta para o problema é a quantidade de valores distintos presentes no vetor.

Para calcularmos quantos valores distintos existem no vetor, podemos utilizar um vetor de booleanos $mark[]$, tal que $mark[i] = 1$ se o valor $i$ está presente no vetor, e $mark[i] = 0$ caso contrário. Este vetor pode ser calculado assim que os números são dados na entrada. Assim, a resposta final para o problema é igual à quantidade de índices de $mark[]$ que são iguais a $1$. Como o vetor $mark[]$ tem tamanho igual ao maior elemento da entrada, a complexidade final da solução é $O(N + M)$, onde $M$ é o valor do maior elemento presente no vetor.

Nota: Uma outra forma de encontrar a quantidade de números distintos no vetor utiliza a estrutura de dados Set. Nesta solução, basta inserir os valores da entrada em um set e, em seguida, imprimir como resposta o tamanho do set. A complexidade desta solução é $O(N \cdot \log_{} N)$, e é uma solução particularmente boa caso os números da entrada possam ser muito grandes.

Segue o código, com comentários, para melhor compreensão do problema:

Problemas Explosivos

Conhecimento Prévio Necessário:

• Estruturas Condicionais
• Loops
• Funções básicas

Para esse problema, podemos usar um laço $while$, para repetirmos o algoritmo do problema, verificando com a estrutura $If/Else$ se $n$ é par ou ímpar com a operação de modularidade, já que com um número ímpar $k$, a operação $k\ \%\ 2$ sempre resultará $1$, e para um número par $k$, a operação $k\ \% \ 2$ sempre resultará $0$. Então, aplicamos com operadores básicos o algoritmo do problema, até que $n$ se-torne $1$. Usaremos uma variável contadora, incrementando-a por um a cada iteração, sendo então o primeiro número da resposta, e uma variável que irá manter o valor máximo atingido usando a função $max$ do C++, o segundo número da resposta.

Segue o código, com comentários, para melhor compreensão do problema:

Eleições da Nlogônia

Conhecimento Prévio Necessário:

• Estruturas Condicionais

Para esse problema temos 4 casos para analisar: ou algum dos 3 candidatos ganham a eleição (caso tenha mais que 50% dos votos, que numericamente representa 500 votos), ou nenhum candidato alcançou mais que 500 votos e isso significa que a eleição irá para o segundo turno. Para sabermos qual a opção correta basta utilizarmos as estruturas condicionais $If/Else$ considerando todos os casos. Segue o código para melhor compreensão: