Problema A: Fibonacciness
Neste problema, recebemos quatro inteiros $a_1, a_2, a_4, a_5$ e devemos escolher um valor para $a_3$ que maximize o número de relações do tipo Fibonacci ($a_i + a_{i+1} = a_{i+2}$). Existem três possíveis equações onde $a_3$ pode influenciar o resultado:
- $a_1 + a_2 = a_3$
- $a_2 + a_3 = a_4$
- $a_3 + a_4 = a_5$
A abordagem mais direta é testar os valores de $a_3$ resultantes de cada uma dessas três equações e verificar qual deles maximiza o total de relações válidas na sequência completa.
Problema B: Farmer John's Card Game
O desafio consiste em determinar uma ordem de jogadores (linhas de uma matriz) tal que, ao jogarem suas cartas de forma cíclica, a sequência resultante seja estritamente crescente. Cada jogador possui $m$ cartas.
Para que uma solução exista, cada jogador deve ter suas cartas distribuídas de forma que, após ordenadas, a diferença entre cartas cnosecutivas do mesmo jogador seja exatamente $n$ (o número total de jogadores). Além disso, o ponto de partida de cada jogador (a menor carta) define sua posição na rodada.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void process_game() {
int n, m;
cin >> n >> m;
vector<vector<int>> decks(n, vector<int>(m));
vector<int> turn_order(n, -1);
bool possible = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) cin >> decks[i][j];
sort(decks[i].begin(), decks[i].end());
if (decks[i][0] < n) {
turn_order[decks[i][0]] = i + 1;
}
}
for (int i = 0; i < n; ++i) {
if (turn_order[i] == -1) possible = false;
}
if (possible) {
for (int i = 0; i < n; ++i) {
int player_idx = turn_order[i] - 1;
for (int j = 1; j < m; ++j) {
if (decks[player_idx][j] != decks[player_idx][j-1] + n) {
possible = false;
break;
}
}
}
}
if (!possible) {
cout << -1 << endl;
} else {
for (int i = 0; i < n; ++i) {
cout << turn_order[i] << (i == n - 1 ? "" : " ");
}
cout << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) process_game();
return 0;
}
Problema C: Game of Mathletes
Dois jogadores escolhem números de um conjunto para formar pares que somam $K$. O objetivo é maximizar o número de pares. Como ambos jogam de forma otimizada para seus respectivos objetivos, a estratégia converge para um algoritmo guloso usando ordenação e dois ponteiros.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve_mathletes() {
int n, k;
cin >> n >> k;
vector<int> nums(n);
for (int &x : nums) cin >> x;
sort(nums.begin(), nums.end());
int left = 0, right = n - 1, pairs = 0;
while (left < right) {
int current_sum = nums[left] + nums[right];
if (current_sum == k) {
pairs++;
left++;
right--;
} else if (current_sum < k) {
left++;
} else {
right--;
}
}
cout << pairs << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve_mathletes();
return 0;
}
Problema D: Subtract Min Adjacent
Podemos subtrair o valor $\min(a_i, a_{i+1})$ de dois elementos adjacentes. Para que o array final seja não-decrescente, devemos processar o array da esquerda para a direita de forma gulosa. Se em algum momento $a_i > a_{i+1}$, torna-se imposssível manter a ordem não-decrescente, pois não há como reduzir $a_i$ sem afetar $a_{i-1}$ ou $a_{i+1}$ de forma prejudicial.
#include <iostream>
#include <vector>
using namespace std;
void check_sortable() {
int n;
cin >> n;
vector<int> vec(n);
for (int &v : vec) cin >> v;
for (int i = 0; i < n - 1; ++i) {
if (vec[i] > vec[i+1]) {
cout << "NO" << endl;
return;
}
vec[i+1] -= vec[i];
vec[i] = 0;
}
cout << "YES" << endl;
}
int main() {
int t;
cin >> t;
while (t--) check_sortable();
return 0;
}
Problema E: Graph Composition
Temos dois grafos, $F$ e $G$. Queremos que $F$ tanha a mesma conectividade de $G$ com o mínimo de operações (remover ou adicionar arestas). A conectividade de $G$ é mandatória.
A estratégia é:
- Usar DSU para identificar os componentes conectados em $G$.
- Para cada aresta em $F$, se ela conecta dois vértices que estão em componentes diferentes em $G$, ela deve ser removida.
- Após as remoções, contamos quantos componentes restaram em $F$ e comparamos com $G$ para determinar quantas adições são necessárias para unir os componentes conforme o grafo $G$.
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
struct DSU {
vector<int> parent;
int components;
DSU(int n) {
parent.resize(n + 1);
iota(parent.begin(), parent.end(), 0);
components = n;
}
int find(int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
bool unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
parent[root_i] = root_j;
components--;
return true;
}
return false;
}
};
void solve_graph() {
int n, m1, m2;
cin >> n >> m1 >> m2;
vector<pair<int, int>> edges_f(m1);
for (int i = 0; i < m1; ++i) cin >> edges_f[i].first >> edges_f[i].second;
DSU dsu_g(n);
for (int i = 0; i < m2; ++i) {
int u, v;
cin >> u >> v;
dsu_g.unite(u, v);
}
DSU dsu_f(n);
int removals = 0;
for (auto &edge : edges_f) {
if (dsu_g.find(edge.first) != dsu_g.find(edge.second)) {
removals++;
} else {
dsu_f.unite(edge.first, edge.second);
}
}
int additions = 0;
// O número de arestas necessárias para conectar componentes de F
// de modo que fiquem iguais aos componentes de G.
for (int i = 1; i <= n; ++i) {
// Lógica simplificada: para cada componente em G, F deve estar unido.
}
// O custo total é remoções + (componentes_F - componentes_G)
cout << removals + (dsu_f.components - dsu_g.components) << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve_graph();
return 0;
}