OBI 2021 - Fase 2 Turno B - Programação Nível Júnior

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Comentário escrito por Anita Almeida, Leonardo Paes e Lúcio Figueiredo

Para conferir a prova na íntegra, clique aqui.

Recorde

Conhecimento prévio necessário:

Estruturas Condicionais

Este problema é bem simples e utiliza apenas a estrutura condicional $if/else$ . Após ler os valores, basta comparar se $r$ é menor que $m$ para determinar se é um recorde mundial, e se $r$ é menor que $l$ para determinar se é um recorde olímpico. Se nenhum dois casos for verdade, basta imprimir $*$ .

A complexidade da solução é $O(1)$ . Segue o código para melhor compreensão da solução:

Anagrama

Conhecimento prévio necessário:

Para resolvermos o problema, basta considerarmos as letras dadas nas strings. Como dito no próprio enunciado, devemos ignorar as vírgulas e os pontos. Para que a frase $A$ seja um anagrama da frase $B$ , é necessário e suficiente que a frequência de cada letra do alfabeto seja a mesma em ambas as frases. Por exemplo, se na frase $A$ a letra $x$ aparece $3$ vezes, na frase $B$ a letra $x$ também deve aparecer 3 vezes. Assim, podemos utilizar um vetor que armazena a frequência de cada letra em uma das strings, e em seguida conferir se tais frequências são idênticas às frequências de cada letra na outra string. Se sim, as frases são anagramas.

Para provarmos tal afirmação, basta supor, por absurdo, que há uma quantidade diferente de uma letra arbitrária em cada frase. Suponha por absurdo que na frase $A$ haja $a$ vezes o caractere $x$ , e na frase $B$ haja $b$ vezes o caractere $x$ , $a \neq b$ . Isso implica que ou $a < b$ ou $b < a$ . Suponhamos sem perda de generalidade que $a < b$ . Então, para formarmos a frase $B$ a partir da frase $A$ , trocando a ordem dos caracteres de $A$ , conseguiremos colocar somente $a$ caracteres $x$ em suas respectivas posições na frase $B$ , o que implica que ainda precisaríamos de $b-a$ caracteres $x$ para completar a frase $B$ . Portanto, a afirmação de que as frequências de cada letra do alfabeto devem ser iguais em ambas as frases está provada por absurdo.

A complexidade final é $O(n)$ . Confira o código abaixo para melhor entendimento:

Potência

Conhecimento prévio necessário:

Estruturas Condicionais
Loops
Apenas por curiosidade, Congruências

Como dito pelo enunciado do problema, a potência é composta por um único dígito. Então, supomos que estamos lendo um inteiro $2324$ . Sabemos que na verdade, queremos $232^4$ . Portanto, uma maneira simples de fazer isso é a seguinte: Após lermos o inteiro $2324$ , utilizaremos a função % $10$ , que nos retornará o número módulo $10$ , ou seja, o resto na divisão por $10$ do número em questão. Note que esse valor sempre será o último dígito do número, ou seja, o dígito das unidades. Valor este que representa a potência do nosso termo. Para eliminarmos o último dígito do número, podemos dividí-lo por 10 e tomar a parte inteira da operação. Em C++, $2324/10 = 232$ , já que o operador $/$ obtém a parte inteira da divisão. Essa operação faz exatamente o que nós precisamos.

A complexidade da solução é $O(n \cdot p)$ . Confira o código abaixo para melhor entendimento:

PS.: Caso deseje ver uma explicação detalhada das operações realizadas acima, clique aqui para conferir a solução do problema Cálculo rápido, da prova do nível P1.

Pesquisa de preços

Conhecimento prévio necessário:

Sejam $A$ e $G$ os preços do litro de álcool e gasolina de um estado, respectivamente. Pela definição dada no enunciado, é vantajoso utilizar o álcool quando $A \leq 70 \% \cdot G \implies A \leq \frac{70}{100} \cdot G \implies$ $100 \cdot A \leq 70 \cdot G$ . Portanto, para checar se é vantajoso utilizar álcool em um dos estados fornecidos na entrada, basta checarmos se a desigualdade obtida é verdadeira, utilizando a estrutura condicional If. Se a desigualdade for verdadeira, imprimimos a sigla do estado na saída.

Porém, precisamos nos atentar a um pequeno detalhe: se não for vantajoso utilizar álcool em nenhum dos $N$ estados, devemos imprimir o caractere $*$ na saída. Para conferir este caso, utilizaremos uma variável booleana $vantajoso$ , declarada inicialmente com o valor $0$ . Se em algum dos $N$ estados fornecidos for vantajoso utilizar álcool, atribuímos o valor $1$ à variável $vantajoso$ . Desta forma, ao fim da leitura dos $N$ estados, basta checarmos se $vantajoso = 0$ ; se sim, imprimimos o caractere $*$ na saída.

Como realizamos operações constantes para cada um dos $N$ estados, a complexidade final da solução é $O(N)$ . Confira o código abaixo para melhor entendimento: