Problema 1: Sobreposição de Retângulos

A resolução baseia-se em uma simulação direta com iteração reversa. Como os tapetes são posicionados sequencialmente, aquele que cobre o ponto de consulta e posui o maior índice será o visível. Armazenamos as coordenadas e dimensões de cada retângulo e percorremos a estrutura de trás para frente, verificando a condição de inclusão do ponto alvo.

#include <iostream>
#include <vector>
struct Rectangle { int left, bottom, width, height; };
int main() {
    int n; std::cin >> n;
    std::vector<Rectangle> carpets(n);
    for (auto &c : carpets) std::cin >> c.left >> c.bottom >> c.width >> c.height;
    int tx, ty; std::cin >> tx >> ty;
    for (int i = n - 1; i >= 0; --i) {
        if (tx >= carpets[i].left && tx <= carpets[i].left + carpets[i].width &&
            ty >= carpets[i].bottom && ty <= carpets[i].bottom + carpets[i].height) {
            std::cout << i + 1 << '\n';
            return 0;
        }
    }
    std::cout << -1 << '\n';
    return 0;
}

Problema 2: Seleção de Hospedarias

O objetivo é identificar pares de estabelecimentos com a mesma classificação cromática onde exista pelo menos uma opção com custo inferior ou igual a um limite definido no intervalo entre eles. A abordagem otimizada utiliza somas de prefixo para validar a condição de preço em tempo constante. Agrupamos os índices por cor e aplicamos uma varredura linear para acumular as combinações válidas, eliminando a necessidade de estruturas de consulta de intervalo complexas.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k, p; cin >> n >> k >> p;
    vector<int> color(n + 1), price(n + 1);
    vector<vector<int>> pos(k);
    vector<int> cheap_prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> color[i] >> price[i];
        cheap_prefix[i] = cheap_prefix[i - 1] + (price[i] <= p ? 1 : 0);
        pos[color[i]].push_back(i);
    }
    long long total_pairs = 0;
    for (int c = 0; c < k; ++c) {
        if (pos[c].size() < 2) continue;
        int left_idx = 0;
        for (int right_idx = 1; right_idx < pos[c].size(); ++right_idx) {
            int l = pos[c][left_idx], r = pos[c][right_idx];
            if (cheap_prefix[r] - cheap_prefix[l] > 0) {
                total_pairs += (long long)(pos[c].size() - right_idx) * (right_idx - left_idx);
                left_idx = right_idx;
            }
        }
    }
    cout << total_pairs << '\n';
    return 0;
}

Problema 3: Quebra-Cabeça Mayan

Este desafio exige busca com retrocesso (backtracking) combinada com simulação de regras de gravidade e eliminação de blocos. A cada movimento lateral válido, o estado do tabuleiro é atualizado: blocos caem para preencher espaços vazios e sequências de três ou mais peças alinhadas são removidas iterativamente. O algoritmo explora a árvore de decisões até a profundidade máxima permitida, restaurando o estado anterior a cada retorno recursivo.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int steps_limit;
int board[6][8];
int history[6][3];
int backup[6][6][8];
bool eliminated[6][8];

void apply_gravity() {
    for (int col = 1; col <= 5; ++col) {
        int write_pos = 1;
        for (int row = 1; row <= 7; ++row) {
            if (board[col][row] != 0) board[col][write_pos++] = board[col][row];
        }
        while (write_pos <= 7) board[col][write_pos++] = 0;
    }
}

bool clear_matches() {
    memset(eliminated, 0, sizeof(eliminated));
    bool found = false;
    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 7; ++j) {
            if (!board[i][j]) continue;
            if (i > 1 && i < 5 && board[i][j] == board[i-1][j] && board[i][j] == board[i+1][j]) {
                eliminated[i-1][j] = eliminated[i][j] = eliminated[i+1][j] = true; found = true;
            }
            if (j > 1 && j < 7 && board[i][j] == board[i][j-1] && board[i][j] == board[i][j+1]) {
                eliminated[i][j-1] = eliminated[i][j] = eliminated[i][j+1] = true; found = true;
            }
        }
    }
    if (!found) return false;
    for (int i = 1; i <= 5; ++i)
        for (int j = 1; j <= 7; ++j)
            if (eliminated[i][j]) board[i][j] = 0;
    return true;
}

void save_state(int depth) {
    for(int i=1;i<=5;++i) for(int j=1;j<=7;++j) backup[depth][i][j] = board[i][j];
}
void restore_state(int depth) {
    for(int i=1;i<=5;++i) for(int j=1;j<=7;++j) board[i][j] = backup[depth][i][j];
}

void dfs(int depth) {
    bool empty = true;
    for(int i=1;i<=5;++i) if(board[i][1]) { empty = false; break; }
    if(empty) {
        for(int i=1;i<=steps_limit;++i) cout << history[i][0] << " " << history[i][1] << " " << history[i][2] << "\n";
        exit(0);
    }
    if(depth > steps_limit) return;
    save_state(depth);
    for(int i=1;i<=5;++i) {
        for(int j=1;j<=7;++j) {
            if(!board[i][j]) continue;
            if(i < 5 && board[i][j] != board[i+1][j]) {
                swap(board[i][j], board[i+1][j]);
                apply_gravity(); while(clear_matches()) apply_gravity();
                history[depth][0]=i-1; history[depth][1]=j-1; history[depth][2]=1;
                dfs(depth+1); restore_state(depth);
            }
            if(i > 1 && board[i-1][j] == 0) {
                swap(board[i][j], board[i-1][j]);
                apply_gravity(); while(clear_matches()) apply_gravity();
                history[depth][0]=i-1; history[depth][1]=j-1; history[depth][2]=-1;
                dfs(depth+1); restore_state(depth);
            }
        }
    }
}
int main() {
    cin >> steps_limit;
    for(int i=1;i<=5;++i) {
        for(int j=1;j<=8;++j) {
            int val; cin >> val;
            if(val==0) break;
            board[i][j] = val;
        }
    }
    memset(history, -1, sizeof(history));
    dfs(1);
    cout << -1 << "\n";
    return 0;
}

Problema 4: Cálculo de Coeficientes Polinomiais

A expansão de $(ax + by)^k$ segue diretamente o Teorema Binomial. O coeficiente do termo $x^n y^m$ é determinado por $\binom{k}{n} \cdot a^n \cdot b^m$. Para evitar overflow e atender aos requisitos do problema, todas as operações são realizadas sob aritmética modular. O triângulo de Pascal é pré-computado para obter as combinações, enquanto a exponenciação rápida calcula as potências das bases em tempo logarítmico.

#include <iostream>
using namespace std;
const int MOD = 10007;
long long mod_pow(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}
int main() {
    long long a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    long long C[1005][1005] = {0};
    C[0][0] = 1;
    for (int i = 1; i <= k; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    long long ans = C[k][n];
    ans = (ans * mod_pow(a, n)) % MOD;
    ans = (ans * mod_pow(b, m)) % MOD;
    cout << ans << "\n";
    return 0;
}

Problema 5: Inspeção de Qualidade

A métrica de avaliação $Y$ apresenta comportamento monotônico decrescente em relação ao parâmetro de limite $W$. Essa propriedade permite a aplicação de busca binária sobre o domínio de $W$. Para cada valor testado, arrays de soma de prefixo acumulam a quentidade e o valor total dos itens que satisfazem a condição de peso, permitindo o cálculo da métrica em tempo linear. O algoritmo rastreia a menor diferença absoluta entre $Y$ e o valor alvo $S$.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct Item { int weight, value; };
struct Range { int l, r; };
int n, m;
long long target_S;
vector<Item> items;
vector<Range> queries;
vector<int> cnt_pref, val_pref;

long long evaluate(int threshold) {
    cnt_pref.assign(n + 1, 0);
    val_pref.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cnt_pref[i] = cnt_pref[i-1] + (items[i].weight >= threshold ? 1 : 0);
        val_pref[i] = val_pref[i-1] + (items[i].weight >= threshold ? items[i].value : 0);
    }
    long long current_Y = 0;
    for (const auto& q : queries) {
        long long c = cnt_pref[q.r] - cnt_pref[q.l - 1];
        long long v = val_pref[q.r] - val_pref[q.l - 1];
        current_Y += c * v;
    }
    return current_Y;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> target_S;
    items.resize(n + 1);
    int min_w = 1e9, max_w = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> items[i].weight >> items[i].value;
        min_w = min(min_w, items[i].weight);
        max_w = max(max_w, items[i].weight);
    }
    queries.resize(m);
    for (int i = 0; i < m; ++i) cin >> queries[i].l >> queries[i].r;

    int low = min_w - 1, high = max_w + 2;
    long long best_diff = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        long long Y = evaluate(mid);
        long long diff = abs(Y - target_S);
        if (best_diff == -1 || diff < best_diff) best_diff = diff;
        if (Y > target_S) low = mid + 1;
        else high = mid - 1;
    }
    cout << best_diff << "\n";
    return 0;
}

Problema 6: Otimização de Transporte Turístico

A minimização do tempo total de viagem é alcançada atrravés de uma estratégia gulosa iterativa. Cada acelerador disponível deve ser alocado no segmento de rota onde a redução de uma unidade de tempo beneficia o maior número de passageiros. O algoritmo calcula o alcance de influência de cada trecho, considerando que o veículo não pode partir antes da chegada do último passageiro em cada parada. Após cada alocação, os horários de chegada são recalculados e o processo se repete até o esgotamento dos recursos.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Passenger { int arrival, start, end; };
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> dist(n);
    for (int i = 1; i < n; ++i) cin >> dist[i];

    vector<Passenger> pass(m);
    vector<int> last_arrival(n + 1, 0);
    vector<int> drop_count(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        cin >> pass[i].arrival >> pass[i].start >> pass[i].end;
        last_arrival[pass[i].start] = max(last_arrival[pass[i].start], pass[i].arrival);
        drop_count[pass[i].end]++;
    }

    vector<int> prefix_pass(n + 1, 0);
    for (int i = 1; i <= n; ++i) prefix_pass[i] = prefix_pass[i-1] + drop_count[i];

    vector<int> bus_arrival(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        bus_arrival[i] = max(bus_arrival[i-1], last_arrival[i-1]) + dist[i-1];
    }

    long long total_time = 0;
    for (const auto& p : pass) total_time += bus_arrival[p.end] - p.arrival;

    while (k-- > 0) {
        vector<int> influence_limit(n + 1);
        influence_limit[n] = n;
        for (int i = n - 1; i >= 1; --i) {
            influence_limit[i] = (bus_arrival[i+1] <= last_arrival[i+1]) ? i + 1 : influence_limit[i+1];
        }
        int best_seg = 0, max_saved = 0;
        for (int i = 1; i < n; ++i) {
            if (dist[i] > 0) {
                int saved = prefix_pass[influence_limit[i]] - prefix_pass[i];
                if (saved > max_saved) {
                    max_saved = saved;
                    best_seg = i;
                }
            }
        }
        if (max_saved == 0) break;
        dist[best_seg]--;
        total_time -= max_saved;
        for (int i = 2; i <= n; ++i) {
            bus_arrival[i] = max(bus_arrival[i-1], last_arrival[i-1]) + dist[i-1];
        }
    }
    cout << total_time << "\n";
    return 0;
}