Problema 1: Detecção de Picos em Grade

A tarefa envolve analisar uma grade bidimensional representando terreno, onde cada célula possui um valor de altitude. O objetivo é determinar, para várias posições iniciais, se existe um pico que satisfaça certas condições geométricas ao navegar predominantemente na direção norte.

Um ponto é considerado um pico local se sua altitude não for inferior à de seus quatro vizinhos imediatos (norte, sul, leste, oeste). Para cada consulta, verificamos uma área em forma de pirâmide invertida estendendo-se a partir da posição do agente em direção ao norte. A busca consiste em iterar sobre os níveis desta pirâmide até encontrar um vértice marcado como pico.

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

using namespace std;

// Estrutura para representar coordenadas
struct Coordenada {
    int x, y;
};

int n, m, k;
vector<vector<int>> altitude;
vector<vector<bool>> ehPico;
vector<Coordenada> posicoes;

void preProcessar() {
    // Mapeia células que atendem à condição de pico local
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (altitude[i][j] >= altitude[i-1][j] && 
                altitude[i][j] >= altitude[i+1][j] && 
                altitude[i][j] >= altitude[i][j-1] && 
                altitude[i][j] >= altitude[i][j+1]) {
                ehPico[i][j] = true;
            } else {
                ehPico[i][j] = false;
            }
        }
    }
}

void resolverConsulta(int startX, int startY) {
    bool encontrado = false;
    int distanciaMaxima = 0;

    // Busca na estrutura piramidal ascendente
    for (int nivel = 0; nivel <= startX; ++nivel) {
        for (int offset = 0; offset <= nivel; ++offset) {
            int colMin = startY - offset;
            int colMax = startY + offset;
            
            // Limitar colunas dentro dos limites da matriz
            colMin = max(1, colMin);
            colMax = min(m, colMax);

            for (int c = colMin; c <= colMax; ++c) {
                int r = startX - nivel;
                if (ehPico[r][c]) {
                    cout << nivel << endl;
                    return;
                }
            }
        }
    }

    // Se nenhum pico foi encontrado na região válida
    cout << "NaoEncontrado" << endl;
}

int main() {
    cin >> n >> m >> k;
    
    altitude.assign(n + 2, vector<int>(m + 2, 0));
    ehPico.assign(n + 2, vector<bool>(m + 2, false));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> altitude[i][j];
        }
    }

    preProcessar();

    for (int i = 0; i < k; ++i) {
        int r, c;
        cin >> r >> c;
        resolverConsulta(r, c);
    }

    return 0;
}

Problema 2: Agendamento Ótimo com Restrições de Tempo

Este problema foca no ordenamento de tarefas que consomem tempo e alteram um saldo acumulado (positivo ou negativo). A estratégia gulosa deve considerar o impacto líquido ($d_i$) e o custo temporal ($t_i$).

Tarefas que aumentam o saldo podem ser processadas prioritariamente, enquanto aquelas que diminuem o saldo exigem cuidado maior. A correção necessária para maximizar as chances de sucesso envolve ordenar as tarefas negativas baseando-se na soma $t_i + b_i$ em ordem decrescente. Isso garante que recursos sejam conservados nas etapas críticas.

#include<iostream>
#include<queue>
#include<vector>
#include<tuple>

using namespace std;

// Tarefa composta por (tempo, impacto)
struct Tarefa {
    int tempo;
    int impacto;
};

void resolverTeste() {
    int z, n, tempoTotal;
    cin >> z;
    
    while(z--) {
        cin >> n >> tempoTotal;
        
        // Filas de prioridade separadas para facilitar lógica gulosa
        priority_queue<pair<int,int>> positivas;
        vector<pair<int,int>> negativas;

        for (int i = 0; i < n; ++i) {
            int t, b;
            cin >> t >> b;
            if (b >= 0) {
                positives.push({-t, b}); // Min heap simulado para tempo menor
            } else {
                negativas.push_back({t, b});
            }
        }

        bool falha = false;

        // Processar incrementos primeiro
        while (!positivas.empty()) {
            auto top = positivas.top();
            int t = -top.first;
            int b = top.second;
            positivas.pop();

            if (tempoTotal < t) {
                falha = true;
                break;
            }
            tempoTotal -= t;
            tempoTotal += b;
        }

        if (!falha) {
            // Ordenar decrementos pela fórmula corrigida: (t + b) descrescente
            // Isso equivale a agrupar tarefas mais lucrativas no fim
            sort(negativas.begin(), negativas.end(), [](const pair<int,int>& a, const pair<int,int>& b){
                return (a.first + a.second) > (b.first + b.second);
            });

            for (const auto& tarefa : negativas) {
                int t = tarefa.first;
                int b = tarefa.second;

                if (tempoTotal < t) {
                    falha = true;
                    break;
                }
                tempoTotal -= t;
                tempoTotal += b;

                // Validade intermediária crítica
                if (tempoTotal <= 0) {
                    falha = true;
                    break;
                }
            }
        }

        if (falha) {
            cout << "-1" << endl;
        } else {
            cout << "+1" << endl;
        }
    }
}

int main() {
    resolverTeste();
    return 0;
}

Problema 3: Verificação de Divisibilidade em Substring

Dada uma sequência numérica longa e um divisor pequeno, é necessário contar subcadieas divisíveis pelo valor dado. O desafio reside na implemetnação eficiente da aritmética de grande precisão (bigint) sem sobrecarga computacional excessiva.

A abordagem envolve pré-calcular os remaiores das divisões utilizando aritmética modular. Ao invés de construir o número completo, mantemos o resto acumulado durante a expansão da subcadeia. A complexidade pode atingir $O(N^2)$ dependendo da implementação, mas otimizações de vetor são essenciais.

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

using namespace std;

// Verifica se o substring s[l..r] é divisível por p usando cálculo incremental
bool verificarDivisibilidade(const string& str, int l, int r, int p) {
    long long moduloAtual = 0;
    int potenciaBase = 1;
    
    // Cálculo reverso para evitar overflow direto
    // Construímos o valor módulo p passo a passo
    for (int i = r; i >= l; --i) {
        int digito = str[i] - '0';
        moduloAtual = (digito * potenciaBase + moduloAtual) % p;
        potenciaBase = (potenciaBase * 10) % p;
    }
    
    return (moduloAtual == 0);
}

int main() {
    int p;
    cin >> p;
    
    string texto;
    cin >> texto;
    int len = texto.length();

    // Pré-calcula divisibilidade para todas as subcadeias possíveis
    // Matriz booleana para cache
    vector<vector<bool>> divisivel(len + 1, vector<bool>(len + 1, false));

    for (int i = 0; i < len; ++i) {
        for (int j = i; j < len; ++j) {
            if (verificarDivisibilidade(texto, i, j, p)) {
                divisivel[i][j] = true;
            }
        }
    }

    int consultas;
    cin >> consultas;

    while(consultas--) {
        int f, t;
        cin >> f >> t;
        int contador = 0;

        // Contagem de pares válidos dentro do intervalo solicitado
        for (int k = f; k <= t; ++k) {
            for (int m = k; m <= t; ++m) {
                if (divisivel[k][m]) {
                    contador++;
                }
            }
        }
        cout << contador << endl;
    }

    return 0;
}