OBI 2021 - Fase 2 Turno B - Programação Nível 1

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, Lúcio Figueiredo e Pedro Racchetti

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:

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, confira a solução do problema Cálculo rápido abaixo.

Cálculo rápido

Conhecimento prévio necessário:

Para resolver este problema, precisamos pensar em como podemos calcular a soma dos dígitos de um número $X$ de forma eficiente. Ou seja, dado um número $X$ , precisamos encontrar cada um dos dígitos de $X$ individualmente; feito isso, é fácil calcular a sua soma.

Algortimo para encontrar os dígitos de $X$

Para extraírmos cada um dos dígitos de $X$ , podemos utilizar o seguinte algoritmo:

Encontre o último dígito $d$ de $X$ ;
Remova o dígito $d$ de $X$ . Denote o número resultante por $X'$ ;
Se $X'$ não possuir dígito algum, termine o algoritmo. Senão, repita o passo 1 com o novo número $X'$ .

Apesar do algoritmo acima estar correto, ainda é necessário descobrir como calcular o último dígito de $X$ e como removê-lo.

Encontrar o último dígito de $X$

Seja $q$ o quociente e $r$ o resto na divisão de $X$ por $10$ . Com esta definição, temos que $X = 10 \cdot q + r$ . Observe que como $10 \cdot q$ é um múltiplo de $10$ , o seu último dígito é igual a $0$ . Além disso, como $r$ é o resto da divisão de $X$ por $10$ , temos que $0 \leq r \leq 9$ . Portanto, podemos concluir que o valor $r$ é igual ao último dígito de $X$ em sua representação decimal! Para observar isto, considere os seguintes exemplos:

$X = 21$ : $q = 2, r = 1$ . Último dígito de $21$ é igual a $1$ .

$X = 343$ : $q = 34, r = 3$ . Último dígito de $343$ é igual a $3$ .

$X =78900$ : $q = 7890, r = 0$ . Último dígito de $78900$ é igual a $0$ .

Com esta observação, concluímos que o último dígito de $X$ é igual a $X \% 10$ , já que o operador $\%$ calcula o resto da divisão de um inteiro por outro.

Remover o último dígito de $X$

Como $r$ é o último dígito de $X$ e $X = 10 \cdot q + r$ , podemos observar que $q$ é igual ao valor $X'$ - ou seja, o valor resultante da remoção do último dígito de $X$ . Novamente, considere os seguintes exemplos para melhor entendimento:

$X = 21$ : $q = 2, r = 1$ . $X'$ é igual a $2$ .

$X = 343$ : $q = 34, r = 3$ . $X'$ é igual a $343$ .

$X =78900$ : $q = 7890, r = 0$ . $X'$ é igual a $7890$ .

Para encontrar o valor $q$ , observe que, por definição, ele é igual a $\frac{X-r}{10}$ . Porém, como $r < 10$ , temos que $\frac{X-r}{10}$ é igual à parte inteira de $\frac{X}{10}$ . Portanto, o valor $X' = q$ é igual a $X / 10$ , já que o operador $/$ calcula a parte inteira da divisão.

Agora que sabemos como executar cada passo do algoritmo apresentado acima, basta o utilizarmos para encontrar a soma dos dígitos de $X$ .

Complexidade do algoritmo

Observe que a complexidade do algoritmo acima é proporcional à quantidade de dígitos de $X$ . Portanto, como a quantidade de dígitos de $X$ é menor ou igual a $\log_{10} X + 1$ , a complexidade final do algoritmo é $O(\log_{} X)$ .

Etapa final

Agora que possuímos um algoritmo eficiente para encontrar as somas dos dígitos de um número inteiro, o que sobra para terminarmos o problema é executá-lo para cada inteiro $X$ entre $A$ e $B$ , utilizando um loop For. Caso a soma dos dígitos de $X$ seja igual a $S$ , adicionamos $1$ em uma variável de resposta, e imprimimos o seu valor ao final do código.

Como executamos o algoritmo acima em todos os números entre $A$ e $B$ , a complexidade final da solução é $O((B-A+1) \cdot \log_{} B) = O(B \cdot \log_{} B)$ . Para melhor entendimento, confira o código abaixo:

Lista palíndroma

Conhecimento prévio necessário:

Antes de resolver o problema, podemos fazer algumas observações iniciais. Para uma subarray $L[i...j]$ , com $i \leq j$ da lista fornecida, note:

Se $i = j$ , então o número de operações necessárias é $0$ ;
Se $L[i] = L[j]$ , não precisamos fazer uma operação, bastando resolver o problema para a subarray $L[i+1...j-1]$ ;
Se $L[i] < L[j]$ , precisamos aumentar $L[i]$ . Dessa forma, precisamos fazer uma operação de contração com o consecutivo de $i$ . A mesma ideia se aplica para o caso de $L[i] > L[j]$ , fazendo a operação entre $j$ e $j-1$ .

Podemos então usar as observações do algoritmo de Two Pointers indicado no link acima, usando como subarray o intervalo $L[1...n]$ - ou seja, a lista inteira. Usaremos então $it1$ como o primeiro ponteiro, começando no início da lista, e $it2$ como segundo ponteiro, começando no fim da lista, até que se encontrem pelas operações acima.