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:

	#include<bits/stdc++.h> // Biblioteca utilizada
	using namespace std;

	int main()
	{
	int r,m,l; // Declaraçãoo de variáveis
	scanf("%d %d %d", &r, &m, &l); // Leitura da entrada
	if(r<m) // Se for menor que o recorde mundial
	{
	printf("RM\n"); // Imprime 'RM'
	}
	else // Senão
	{
	printf("\n"); // Imprime ''
	}
	if(r<l) // Se for menor que o recorde olímpico
	{
	printf("RO\n"); // Imprime 'RO'
	}
	else // Senão
	{
	printf("\n"); // Imprime ''
	}
	return 0; // Retorna a 0
	}

view raw recorde.cpp hosted with

by GitHub

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.

	#include<bits/stdc++.h>
	using namespace std;
	int freq[26];
	int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	int soma = 0;
	for(int i=1; i<=n; i++){
	int num;
	cin >> num;
	int p = num%10;
	num /= 10;
	int valor = 1;
	for(int j=1; j<=p; j++){
	valor *= num;
	}
	soma += valor;
	}
	cout << soma << "\n";
	return 0;
	}

view raw Potencia.cpp hosted with

by GitHub

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:

	// Comentário NOIC - OBI Fase 2 P1/P2 - Cálculo rápido
	// Complexidade: O(B * log B)
	// Escrito por Lúcio Figueiredo

	#include <bits/stdc++.h>

	using namespace std;

	// calcula a soma dos dígitos de x
	int get_soma(int x)
	{
	int soma = 0;

	while (x > 0)
	{
	soma += x%10; // último dígito de x
	x /= 10; // removemos o último dígito de x e continuamos
	}

	return soma;
	}

	int main(void)
	{
	int S, A, B;
	scanf("%d %d %d", &S, &A, &B);

	int ans = 0;

	// iteramos por cada valor em [A, B]
	for (int i = A; i <= B; i++)
	if (get_soma(i) == S)
	ans++;

	printf("%d\n", ans);
	}

view raw calculo.cpp hosted with

by GitHub

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:

	#include<bits/stdc++.h>
	using namespace std;
	const int MAXN = 1e6 + 10;
	typedef long long ll;

	ll l[MAXN];
	int n;

	int main(){

	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
	scanf("%lld", &l[i]);
	}
	//Iniciamos os iteradores e a resposta
	int it1 = 1, it2 = n;
	int ans = 0;
	while(it1 < it2){
	if(l[it1] == l[it2]){
	it1++;
	it2--;
	continue;
	}
	//Sempre que precisamos fazer uma operação,
	//incrementamos a resposta
	if(l[it1] > l[it2] ){
	l[it2-1] += l[it2];
	it2--;
	ans++;
	}
	else{
	l[it1+1] += l[it1];
	it1++;
	ans++;
	}
	}
	//Imprmimos a resposta
	printf("%d\n", ans);
	}

view raw lista.cpp hosted with

by GitHub

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

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

Recorde

Potência

Cálculo rápido

Algortimo para encontrar os dígitos de XX

Encontrar o último dígito de XX

Remover o último dígito de XX

Complexidade do algoritmo

Etapa final

Lista palíndroma

Algortimo para encontrar os dígitos de $X$

Encontrar o último dígito de $X$

Remover o último dígito de $X$