Problema 1: Manipulação de Sequências e Ponteiros Duplos

O primeiro desafio requer a análise de operações em sequências binárias. Ao inverter a estrutura de dados original, a consulta para um índice específico resume-se a determinar o custo mínimo para converter um prefixo em zeros. A implementação utiliza um ponteiro auxiliar para monitorar a extremidade de blocos contíguos de elementos '1'. Como ambos os ponteiros avançam monotonicamente, a complexidade temporal é estritamente linear, resultando em $O(n)$.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int length;
    if (!(cin >> length)) return 0;
    string sequence;
    cin >> sequence;
    
    reverse(sequence.begin(), sequence.end());
    sequence = " " + sequence; 
    
    bool all_zeros = true;
    for (int i = 1; i <= length; ++i) {
        if (sequence[i] == '1') {
            all_zeros = false;
            break;
        }
    }
    
    int right_bound = 1;
    long long operations_cost = 0;
    
    for (int i = 1; i <= length; ++i) {
        right_bound = max(right_bound, i);
        while (right_bound < length && sequence[right_bound + 1] == '1') {
            right_bound++;
        }
        
        if (sequence[i] == '1') {
            if (right_bound == length) {
                all_zeros = true;
            } else {
                operations_cost += (right_bound - i + 1);
                sequence[right_bound + 1] = '1';
                right_bound++;
            }
        }
        
        if (all_zeros) operations_cost = -1;
        cout << operations_cost << (i == length ? "" : " ");
    }
    cout << "\n";
    return 0;
}</algorithm></string></iostream>

Problema 2: Matemática Combinatória e Configurações de Grade

A resolução deste problema baseia-se em matemática combinatória. Uma configuração de tabuleiro considerada válida possui dois estados iniciais distintos para o canto superior esquerdo. A transição para um estado que exige $d$ modificações é calculada através de coeficientes binomiais $C_{r \times c}^d$. Utiliza-se o Triângulo de Pascal para pré-computar as combinações sob aritmética modular. Condições de contorno estritas devem ser aplicadas: se o total de células for exatamente o dobro das modificações, o multiplicador de simetria é removido; se for inferior, a resposta é nula.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long rows, cols, diffs;
    if (!(cin >> rows >> cols >> diffs)) return 0;
    
    long long total_cells = rows * cols;
    
    if (total_cells < 2 * diffs) {
        cout << 0 << "\n";
        return 0;
    }
    
    vector<vector long="">> pascal(total_cells + 1, vector<long long="">(diffs + 1, 0));
    
    for (int i = 0; i <= total_cells; ++i) {
        pascal[i][0] = 1;
        for (int j = 1; j <= min((long long)i, diffs); ++j) {
            pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][j - 1]) % MOD;
        }
    }
    
    long long combinations = pascal[total_cells][diffs];
    
    if (total_cells == 2 * diffs) {
        cout << combinations << "\n";
    } else {
        cout << (combinations * 2) % MOD << "\n";
    }
    
    return 0;
}</long></vector></algorithm></vector></iostream>

Problema 3: Busca em Largura com Poda de Estados

Trata-se de um algoritmo de Busca em Largura (BFS) aplicado a uma matriz, onde cada movimento permite avançar até $k$ passos em uma direção linear. Uma otimização crucial para evitar tempo limite excedido é a poda de distância: ao expandir um salto, se a distância acumulada até a célula atual for maior ou igual à distância previamente registrada na célula de destino, a iteração naquela direção é imediatamente abortada.

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

struct Coordinate {
    int r, c;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, max_step;
    if (!(cin >> n >> m >> max_step)) return 0;
    
    int start_r, start_c, target_r, target_c;
    cin >> start_r >> start_c >> target_r >> target_c;
    
    vector<string> grid(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> grid[i];
        grid[i] = " " + grid[i];
    }
    
    vector<vector>> dist(n + 1, vector<int>(m + 1, 1e9));
    vector<vector>> in_queue(n + 1, vector<bool>(m + 1, false));
    queue<coordinate> q;
    
    q.push({start_r, start_c});
    dist[start_r][start_c] = 0;
    in_queue[start_r][start_c] = true;
    
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};
    
    while (!q.empty()) {
        Coordinate curr = q.front();
        q.pop();
        in_queue[curr.r][curr.c] = false;
        
        if (curr.r == target_r && curr.c == target_c) {
            cout << dist[curr.r][curr.c] << "\n";
            return 0;
        }
        
        for (int dir = 0; dir < 4; ++dir) {
            for (int step = 1; step <= max_step; ++step) {
                int next_r = curr.r + dr[dir] * step;
                int next_c = curr.c + dc[dir] * step;
                
                if (next_r < 1 || next_r > n || next_c < 1 || next_c > m || grid[next_r][next_c] == '@') {
                    break;
                }
                
                if (dist[curr.r][curr.c] >= dist[next_r][next_c]) {
                    break; // Poda de estado
                }
                
                if (dist[curr.r][curr.c] + 1 < dist[next_r][next_c]) {
                    dist[next_r][next_c] = dist[curr.r][curr.c] + 1;
                    if (!in_queue[next_r][next_c]) {
                        in_queue[next_r][next_c] = true;
                        q.push({next_r, next_c});
                    }
                }
            }
        }
    }
    
    cout << -1 << "\n";
    return 0;
}</coordinate></bool></vector></int></vector></string></queue></string></vector></iostream>

Problema 4: Programação Dinâmica Multidimensional

Esta é uma variação do problema da mochila. A abordagem requer a ordenação prévia dos elementos e o uso de uma tabela dinâmica tridimensional que rastreia a capacidade de peso, o limite de itens extras e o estado de processamento. A estrutura garante que as restrições de capacidade máxima sejam consolidadas de forma otimizada a cada iteração de inclusão.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int items_count, capacity, extra_limit;
    if (!(cin >> items_count >> capacity >> extra_limit)) return 0;
    
    vector<long long=""> weights(items_count);
    for (int i = 0; i < items_count; ++i) {
        cin >> weights[i];
    }
    
    sort(weights.begin(), weights.end());
    
    const long long INF = -1e18;
    vector<vector long="">>> dp(capacity + 1, vector<vector long="">>(extra_limit + 1, vector<long long="">(2, INF)));
    dp[0][0][0] = 0;
    
    for (int i = 0; i < items_count; ++i) {
        long long current_weight = weights[i];
        
        vector<vector long="">> max_prev(capacity + 1, vector<long long="">(extra_limit + 1, INF));
        for (int w = 0; w <= capacity; ++w) {
            for (int e = 0; e <= extra_limit; ++e) {
                max_prev[w][e] = max(dp[w][e][0], dp[w][e][1]);
            }
        }
        
        for (int w = 0; w <= capacity; ++w) {
            for (int e = 0; e <= extra_limit; ++e) {
                if (max_prev[w][e] == INF) continue;
                
                int new_w = min((long long)capacity, w + current_weight);
                dp[new_w][e][1] = max(dp[new_w][e][1], max_prev[w][e] + current_weight);
                
                if (e < extra_limit) {
                    dp[w][e + 1][0] = max(dp[w][e + 1][0], max_prev[w][e] + current_weight);
                }
            }
        }
    }
    
    long long optimal_result = 0;
    for (int w = 0; w <= capacity; ++w) {
        for (int e = 0; e <= extra_limit; ++e) {
            optimal_result = max({optimal_result, dp[w][e][0], dp[w][e][1]});
        }
    }
    
    cout << optimal_result << "\n";
    return 0;
}</long></vector></long></vector></vector></long></algorithm></vector></iostream>

Problema 5: Janela Deslizante Bidimensional

A estratégia ideal para este problema consiste na aplicação da técnica de janela deslizante em duas dimensões (2D sliding window). Este método é projetado para processar consultas de submatrizes contíguas de forma incremental, evitando a recomputação de áreas sobrepostas ao trensitar pelas linhas e colunas da grade.

Problema 6: Programação Dinâmica e Somas de Prefixo

O último problema envolve DP combinatória. Inicialmente, calcula-se o número de maneiras de cada indivíduo atingir uma pontuação específica. Em seguida, esses valores são propagados para um estado global. Como a transição ingênua resultaria em complexidade quadrática, aplica-se uma otimização baseada em somas de prefixo, permitindo calcular as combinações válidas de estados anteriores em tempo linear.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1e9 + 7;

void process_test_case() {
    int p1, p2, p3, n;
    cin >> p1 >> p2 >> p3 >> n;
    int max_possible_score = p1 + p2 + p3;
    
    vector<long long=""> global_dp(max_possible_score + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        string status;
        cin >> status;
        
        vector<long long=""> ways(max_possible_score + 1, 0);
        bool is_first_active = true;
        
        for (int j = 0; j < 3; ++j) {
            if (status[j] == 'Y') {
                int limit = (j == 0) ? p1 : (j == 1) ? p2 : p3;
                if (is_first_active) {
                    for (int k = 1; k <= limit; ++k) ways[k] = 1;
                    is_first_active = false;
                } else {
                    vector<long long=""> prefix(max_possible_score + 1, 0);
                    for (int k = 1; k <= max_possible_score; ++k) {
                        prefix[k] = (prefix[k - 1] + ways[k]) % MOD;
                    }
                    for (int k = 1; k <= max_possible_score; ++k) {
                        int lower_bound = max(0, k - limit);
                        ways[k] = (prefix[k - 1] - prefix[lower_bound] + MOD) % MOD;
                    }
                }
            }
        }
        
        if (is_first_active) ways[0] = 1;
        
        if (i > 0) {
            vector<long long=""> prefix_global(max_possible_score + 1, 0);
            for (int j = 0; j <= max_possible_score; ++j) {
                prefix_global[j] = ((j > 0 ? prefix_global[j - 1] : 0) + global_dp[j]) % MOD;
            }
            for (int j = 0; j <= max_possible_score; ++j) {
                long long sum_strictly_greater = (prefix_global[max_possible_score] - prefix_global[j] + MOD) % MOD;
                global_dp[j] = (sum_strictly_greater * ways[j]) % MOD;
            }
        } else {
            global_dp = ways;
        }
    }
    
    long long total_valid_configurations = 0;
    for (int i = 0; i <= max_possible_score; ++i) {
        total_valid_configurations = (total_valid_configurations + global_dp[i]) % MOD;
    }
    
    cout << total_valid_configurations << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int test_cases;
    if (cin >> test_cases) {
        while (test_cases--) {
            process_test_case();
        }
    }
    return 0;
}</long></long></long></long></string></vector></iostream>