A
Problema
Dados dois números inteiros a e b, encontre quantos valores inteiros distintos de x existem tais que os três números (considerando a, b e x em qualquer ordem) formem uma progressão aritmética. Ou seja, para alguma permutação (p, q, r) desses três números, a condição q - p = r - q é satisfeita. Pares ordenados (q, p, r) que representam a mesma progressão aritmética são contados apenas uma vez.
Solução
A solução mais direta envolve classificar os casos. Um método mais simples é iterar por todos os valores possíveis de x em um intervalo razoável (por exemplo, de -200 a 200) e usar um mapa para verificar permutações únicas. A resposta pode ser calculada verificando as condições manualmente.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int a, b;
cin >> a >> b;
int ans = 1;
if ((a + b) % 2 == 0 && (a + b) / 2 != a && (a + b) / 2 != b) ans++;
if (a != b) ans++;
cout << ans << "\n";
}
B
Problema
Você está tocando piano com as duas mãos, que se movem independentemente. Uma sequência de N notas é fornecida, cada uma especificando uma posição (coordenada) e qual mão (L para esquerda, R para direita) deve tocar aquela nota. A fadiga total é a soma das distâncias absolutas percorridas por cada mão. Você pode escolher a posição inicial de cada mão. Minimize a fadiga total.
Solução
A posição inicial ideal para cada mão é simplesmente a primeira posição que aquela mão toca na sequência. Depois disso, basta somar as distâncias absolutas entre posições consecutivas para cada mão separadamente.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n; cin >> n;
vector<int> left, right;
for (int i = 0; i < n; i++) {
int pos; char hand;
cin >> pos >> hand;
if (hand == 'L') left.push_back(pos);
else right.push_back(pos);
}
ll fatigue = 0;
for (size_t i = 1; i < left.size(); i++) fatigue += abs(left[i] - left[i-1]);
for (size_t i = 1; i < right.size(); i++) fatigue += abs(right[i] - right[i-1]);
cout << fatigue << "\n";
}
C
Problema
Dada uma sequência de inteiros positivos a[1..N], conte o número de pares ordenados (l, r) com 1 ≤ l ≤ r ≤ N tais que a subseqüência a[l..r] é uma progressão aritmética.
Solução
Uma progressão aritmética tem diferenças constantes entre elementos consecutivos. Calculamos o array de diferenças d[i] = a[i] - a[i-1] para i >= 2. Então, contamos segmentos consecutivos de igual diferença. Se um segmento tem comprimento k, ele contribui com k*(k+1)/2 para o total (considerando subsegmentos de tamanho 2 ou mais). Cada elemento individual já conta como N pares (i,i).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n; cin >> n;
vector<ll> a(n);
for (auto &x : a) cin >> x;
if (n == 1) {
cout << 1 << "\n";
return 0;
}
vector<ll> diff(n);
for (int i = 1; i < n; i++) diff[i] = a[i] - a[i-1];
ll ans = n;
ll cur_len = 1;
for (int i = 2; i < n; i++) {
if (diff[i] == diff[i-1]) cur_len++;
else {
ans += cur_len * (cur_len + 1) / 2;
cur_len = 1;
}
}
ans += cur_len * (cur_len + 1) / 2;
cout << ans << "\n";
}
D
Problema
Você deve derrotar monstros em ordem, do primeiro ao N-ésimo. Derrotar o i-ésimo monstro concede a[i] de experiência. Você pode pular qualquer monstro. Se o k-ésimo monstro que você derrotar (na sua sequência pessoal) tiver k par, a experiência ganha é dobrada. Maximize a experiência total.
Solução
Use programação dinâmica. even[i]: experiência máxima considerando os primeiros i monstros, tendo derrotado uma quantidade par. odd[i]: analogamente para quantidade ímpar. A transição é:
odd[i] = max(odd[i-1], even[i-1] + a[i])even[i] = max(even[i-1], odd[i-1] + 2*a[i])
Inicialize odd[0] = -inf e even[0] = 0.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = -1e18;
int main() {
int n; cin >> n;
vector<ll> a(n);
for (auto &x : a) cin >> x;
vector<ll> odd(n+1, NEG_INF), even(n+1, 0);
for (int i = 1; i <= n; i++) {
odd[i] = max(odd[i-1], even[i-1] + a[i-1]);
even[i] = max(even[i-1], odd[i-1] + 2 * a[i-1]);
}
cout << max(odd[n], even[n]) << "\n";
}
E
Problema
Dado um grafo não-direcionado com pesos nas arestas, você deve responder a Q consultas. Cada consulta fornece K arestas (identificadas por índice). Para cada consulta, encontre a menor distância de 1 a N que obrigatoriamente percorre cada uma das K arestas pelo menos uma vez (em qualquer direção). O grafo tem até 400 vértices e 2e5 arestas. K é pequeno (até 5). O número de consultas é até 3000.
Solução
Pré-compute as distâncias mínimas entre todos os pares de vértices com Floyd-Warshall. Para cada consulta, como o número de arestas obrigatórias K é muito pequeno, podemos permutar a ordem em que as percorremos e a direção de cada uma (de u para v ou vice-versa). Para cada permutação e escolha de direção, calcule a distância total como: distância de 1 ao primeiro vértice da primeira aresta (conforme a direção escolhida) + soma dos pesos das arestas + distâncias entre vértices consecutivos (conforme a ordem) + distância do último vértice a N. Use next_permutation e um DFS ou iteração para testar as direções.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
struct Edge { int u, v; ll w; };
int main() {
int n, m; cin >> n >> m;
vector<vector<ll>> dist(n+1, vector<ll>(n+1, INF));
for (int i = 1; i <= n; i++) dist[i][i] = 0;
vector<Edge> edges(m+1);
for (int i = 1; i <= m; i++) {
int u, v; ll w; cin >> u >> v >> w;
edges[i] = {u, v, w};
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
// Floyd-Warshall
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
int q; cin >> q;
while (q--) {
int k; cin >> k;
vector<int> idx(k);
for (int i = 0; i < k; i++) cin >> idx[i];
sort(idx.begin(), idx.end());
ll ans = INF;
do {
// iterate over 2^k directions
for (int mask = 0; mask < (1 << k); mask++) {
int cur = 1;
ll total = 0;
for (int i = 0; i < k; i++) {
Edge e = edges[idx[i]];
int from, to;
if (mask & (1 << i)) { from = e.u; to = e.v; }
else { from = e.v; to = e.u; }
total += dist[cur][from] + e.w;
cur = to;
}
total += dist[cur][n];
ans = min(ans, total);
}
} while (next_permutation(idx.begin(), idx.end()));
cout << ans << "\n";
}
}
F
Problema
Você está em uma grade de tamanho H x W e só pode se mover para a direita ou para baixo. Existem N células especiais marcadas. Encontre o número máximo de células especiais que podem ser visitadas em um caminho de (1,1) a (H,W) e imprima um caminho de comprimento mínimo (usando 'D' para baixo e 'R' para direita) que atinge esse máximo. H,W podem ser até 2e5, e N até 2e5.
Solução
Como o movimento é restrito a direita/baixo, a ordem natural é processar as células por linha (ou coluna). Para cada célula especial (x,y), a DP é: dp[x][y] = max(dp[x'][y'] para x' < x e y' < y) + 1. Como o grid é grande, comprimimos as coordenadas das células especiais. Processamos as células ordenadas por x crescente. Dentro do mesmo x, devemos processar em ordem crescente de y (importante!). Para cada y, precisamos do máximo dp para y' <= y das células já processadas (que têm x menor). Isso pode ser feito com uma BIT ou segment tree. Após obter a DP máxima, para reconstruir o caminho, armazenamos o predecessor de cada célula e depois geramos a sequência de movimentos entre células consecutivas no caminho incluindo (1,1) e (H,W).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXC = 200005;
int h, w, n;
vector<pair<int,int>> points;
map<int,int> compX, compY;
struct BIT {
vector<pair<int,int>> tree; // max value, index
int sz;
BIT(int n) : sz(n), tree(n+1, {0,0}) {}
void update(int idx, pair<int,int> val) {
while (idx <= sz) {
if (val.first > tree[idx].first) tree[idx] = val;
idx += idx & -idx;
}
}
pair<int,int> query(int idx) {
pair<int,int> res = {0,0};
while (idx > 0) {
if (tree[idx].first > res.first) res = tree[idx];
idx -= idx & -idx;
}
return res;
}
};
int main() {
cin >> h >> w >> n;
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
points.push_back({x, y});
}
// coordinate compression
vector<int> xs, ys;
for (auto &p : points) {
xs.push_back(p.first);
ys.push_back(p.second);
}
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
for (int i = 0; i < (int)xs.size(); i++) compX[xs[i]] = i+1;
for (int i = 0; i < (int)ys.size(); i++) compY[ys[i]] = i+1;
vector<vector<pair<int,int>>> byX(xs.size()+1);
for (int i = 0; i < n; i++) {
int cx = compX[points[i].first];
int cy = compY[points[i].second];
byX[cx].push_back({cy, i});
}
BIT bit(ys.size());
vector<int> dp(n, 0), pre(n, -1);
for (int i = 1; i <= (int)xs.size(); i++) {
sort(byX[i].begin(), byX[i].end());
vector<tuple<int,int,int>> updates; // y, dp, idx
for (auto &p : byX[i]) {
int y = p.first, idx = p.second;
auto best = bit.query(y);
dp[idx] = best.first + 1;
pre[idx] = best.second;
updates.push_back({y, dp[idx], idx});
}
for (auto &[y, d, idx] : updates) {
bit.update(y, {d, idx});
}
}
// find maximum dp
int max_dp = 0, best_idx = -1;
for (int i = 0; i < n; i++) {
if (dp[i] > max_dp) {
max_dp = dp[i];
best_idx = i;
}
}
cout << max_dp << "\n";
// reconstruct path
vector<int> path_idx;
while (best_idx != -1) {
path_idx.push_back(best_idx);
best_idx = pre[best_idx];
}
reverse(path_idx.begin(), path_idx.end());
// add start and end
int cur_x = 1, cur_y = 1;
for (int idx : path_idx) {
int nx = points[idx].first, ny = points[idx].second;
while (cur_x < nx) { cout << 'D'; cur_x++; }
while (cur_y < ny) { cout << 'R'; cur_y++; }
}
while (cur_x < h) { cout << 'D'; cur_x++; }
while (cur_y < w) { cout << 'R'; cur_y++; }
cout << "\n";
}
G
Probleam
Dada uma árvore enraizada em 1 com arestas ponderadas, dois jogadores A e B jogam um jogo. A escolhe um conjunto S de k vértices (para k = 1..N). B então inicia no vértice 1, percorre todos os vértices de S (em qualquer ordem) e retorna a 1, minimizando a distância total percorrida. A quer maximizar essa distância mínima. Para cada k, determine o valor do jogo (a distância que B percorrerá sob jogada ótima de ambos).
Solução
A distância mínima que B percorrerá dado um conjunto S é 2 * (soma dos pesos das arestas na união dos caminhos de 1 para cada vértice em S). Isso equivale a percorrer uma DFS que visita todos os vértices de S. A estratégia ótima de A é adicionar ao conjunto, um de cada vez, o vértice cujo caminho até 1 adiciona a maior quantidade de novas arestas (não coebrtas anteriormente). Portanto, precisamos de uma estrutura que, dado um estado (arestas já cobertas), encontre o vértice mais distante de 1 em termos de arestas não cobertas, e então marque o caminho desse vértice até 1 como coberto. Construímos a árvore, computamos a ordem Euler e sub-árvores, e usamos uma segment tree para suportar atualizações de caminho. Como cada aresta é coberta apenas uma vez, a complexidade é O(N log N).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll w; };
vector<vector<Edge>> g;
vector<int> tin, tout, parent;
vector<ll> depth, edge_weight;
int timer = 0;
void dfs(int u, int p, ll d, ll w) {
tin[u] = ++timer;
depth[timer] = d;
parent[timer] = (p == -1 ? 0 : tin[p]);
edge_weight[timer] = w;
for (auto &e : g[u]) {
if (e.to == p) continue;
dfs(e.to, u, d + e.w, e.w);
}
tout[tin[u]] = timer;
}
struct SegTree {
struct Node { ll max_val; int id; ll lazy; };
vector<Node> tree;
int n;
SegTree(int n) : n(n) { tree.resize(4*n); }
void build(int v, int l, int r) {
if (l == r) { tree[v] = {depth[l], l, 0}; return; }
int mid = (l+r)/2;
build(v*2, l, mid);
build(v*2+1, mid+1, r);
pull(v);
}
void apply(int v, ll x) {
tree[v].max_val += x;
tree[v].lazy += x;
}
void push(int v) {
if (tree[v].lazy) {
apply(v*2, tree[v].lazy);
apply(v*2+1, tree[v].lazy);
tree[v].lazy = 0;
}
}
void pull(int v) {
if (tree[v*2].max_val > tree[v*2+1].max_val) {
tree[v] = {tree[v*2].max_val, tree[v*2].id, 0};
} else {
tree[v] = {tree[v*2+1].max_val, tree[v*2+1].id, 0};
}
}
void update(int v, int l, int r, int ql, int qr, ll x) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) { apply(v, x); return; }
push(v);
int mid = (l+r)/2;
update(v*2, l, mid, ql, qr, x);
update(v*2+1, mid+1, r, ql, qr, x);
pull(v);
}
pair<ll,int> query(int v, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return {-1e18, -1};
if (ql <= l && r <= qr) return {tree[v].max_val, tree[v].id};
push(v);
int mid = (l+r)/2;
auto left = query(v*2, l, mid, ql, qr);
auto right = query(v*2+1, mid+1, r, ql, qr);
return (left.first > right.first) ? left : right;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
g.resize(n+1);
for (int i = 0; i < n-1; i++) {
int u, v; ll w; cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
tin.resize(n+1);
tout.resize(n+1);
parent.resize(n+1);
depth.resize(n+1);
edge_weight.resize(n+1);
dfs(1, -1, 0, 0);
SegTree seg(n);
seg.build(1, 1, n);
vector<bool> covered(n+1, false);
covered[1] = true;
ll ans = 0;
for (int k = 1; k <= n; k++) {
auto [val, id] = seg.query(1, 1, n, 1, n);
ans += 2 * val;
cout << ans << "\n";
int cur = id;
while (!covered[cur]) {
covered[cur] = true;
seg.update(1, 1, n, cur, tout[cur], -edge_weight[cur]);
cur = parent[cur];
}
}
}