Comentário OBI 2024 Segunda Fase A – Problema “Dança de Formatura” (PS)

1 de setembro de 2024

—

por

Henrique Akabane Cunha Vianna

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