OBI 2024 - Fase 2 - Programação Nível 1

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.

Avenida

Comentário por Henrique Vianna

Perceba que há duas rotas que podem ser escolhidas:

Ir ao último ponto de ônibus anterior à escola e andar o que faltar, ou seja, $D \% 400$ metros.
Ir ao primeiro ponto de ônibus posterior à escola e "voltar" andando, ou seja, $400 - D \% 400$ metros.

Portanto, a distância mínima que Luiza precisará andar será simplesmente o mínimo entre esses dois valores.

Segue o código:

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

	int main()
	{
	int d; cin >> d;
	cout << min(d % 400, 400 - d % 400) << '\n';
	}

view raw

Avenida.cpp

hosted with ❤ by GitHub

Alfabeto

Comentário por Murilo Maeda Kataoka

Conhecimento necessário

Para esse problema, só precisamos de uma estrutura que seja capaz de nos dizer se um certo caracter está ou não no alfabeto. Uma estrutura que faz exatamente isso é o map, da STL do C++. Com ele, basta passarmos pelos caracteres do alfabeto alienígena e marcar $map[caracter] = true$ . Depois, quando estivermos passando pela mensagem, basta ver se o map do caracter em questão foi ou não ativado.

Segue o código:

	#include<bits/stdc++.h>
	using namespace std;
	int main()
	{
	cin.tie(0)->sync_with_stdio(0);

	int N,K; cin >> N >> K;

	string alfabeto, mensagem; cin >> alfabeto >> mensagem;

	map<char,bool> marc;

	for(char cur : alfabeto)
	{
	marc[cur] = true;
	}

	bool eh = true;

	for(char cur : mensagem)
	{
	if(!marc[cur])
	eh = false;
	}

	if(eh) cout << "S\n";
	else cout << "N\n";
	}

view raw

Alfabeto.cpp

hosted with ❤ by GitHub

Dança de Formatura

Comentário por Henrique Vianna

Conhecimento prévio necessário:

Perceba que o número do aluno na linha $i$ e coluna $j$ é dado por $(i - 1)*M+j$ inicialmente. Analisando essa "fórmula", percebe-se que quando ocorre a troca de duas linhas, mudamos apenas o valor pelo qual $M$ é multiplicado. De forma análoga, quando ocorre a troca de duas colunas, há uma alteração apenas na constante (inicialmente $j$ ) que somamos. Então, basta mantermos, para cada linha, o valor $X[i]$ , pelo qual devemos multiplicar $M$ e, para cada coluna, a constante $Y[j]$ que devemos somar. Inicialmente, temos $X[i]=i$ para todo $1\leq i \leq N$ e $Y[j] = j$ para todo $1 \leq j \leq M$ . Numa operação, basta darmos um swap nos valores em questão. Ao final, basta imprimirmos $(X[i] - 1) * M + Y[j]$ para cada posição $(i, j)$ .

Segue o código:

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

	int32_t main(void)
	{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, q; cin >> n >> m >> q;

	vector<int> x(n + 1), y(m + 1);

	iota(x.begin(), x.end(), 0);
	iota(y.begin(), y.end(), 0);

	while(q--)
	{
	char op; cin >> op;
	int a, b; cin >> a >> b;

	if(op == 'L') swap(x[a], x[b]);
	else swap(y[a], y[b]);
	}

	for(int i = 1; i <= n; i++)
	{
	for(int j = 1; j <= m; j++)
	cout << (x[i] - 1) * m + y[j] << ' ';

	cout << '\n';
	}
	}

view raw

dancaDeFormatura.cpp

hosted with ❤ by GitHub

Concatena Dígitos

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Somas de prefixos

Vamos chegar em uma fórmula para resolver a pergunta $[L, R]$ . Seja $a_i$ o i-ésimo dígito. Veja um número $a_i$ entre $[L, R]$ , tem duas possibilidades para ele:

Ele pode ser um algarismo da dezena, ou seja, ele contribui a soma total com $10 \times a_i$ . E caso eu escolha esse número para ser o da dezena, temos $R-L+1-1= R-L$ possibilidades de números para as unidades (Quantidade de números entre $L$ e $R$ , sem contar o próprio $a_i$ ), portanto, temos $R-L$ números com $a_i$ sendo a dezena. Portanto, esse caso adiciona $10 \times a_i \times (R-L)$ nesse caso.
Agora, esse mesmo número também pode ser um algarismo da unidade, ou seja, ele contribui a soma total com $a_i$ . Pelo mesmo argumento acima, temos $R-L$ números com $a_i$ sendo a unidade. Portanto, esse cado adiciona $a_i \times (R-L)$ .

Portanto, somando esses dois casos, para cada $a_i$ , eles contribuem na resposta o valor $11 \times (R-L) \times a_i$ . Fazendo isso para todo $a_i$ entre $[L, R]$ , temos que a resposta de uma query é $11 \times (R-L) \times (a_L + \cdots + a_R)$ . Agora, usando a técnica de soma de prefixos, faça $p_i = a_1+a_2+\cdots+a_i$ , e então, a resposta para query é $11(R-L)(p_R-p_{L-1})$ , e conseguimos responder essa query em $O(1)$ .

Clique aqui para ver o código