Comentário NOIC OBI 2021 – Fase 2 Turno B – Programação Nível 1

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:

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:

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:

  1. Encontre o último dígito $$d$$ de $$X$$;
  2. Remova o dígito $$d$$ de $$X$$. Denote o número resultante por $$X’$$;
  3. 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.

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