Problema A - Buildings

O objetivo é identificar o índice do primeiro edifício cuja altura seja estritamente maior que a do edifício inicial da sequência. Caso nenhum edifício satisfaça essa condição, o algoritmo deve retornar -1. A abordagem processa os dados de entrada em tempo linear, mantendo a altura de referência e verificando cada valor subsequente.

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int totalBuildings;
    if (!(cin >> totalBuildings)) return 0;
    
    int referenceHeight;
    cin >> referenceHeight;
    
    int targetIndex = -1;
    for (int i = 2; i <= totalBuildings; ++i) {
        int currentHeight;
        cin >> currentHeight;
        if (targetIndex == -1 && currentHeight > referenceHeight) {
            targetIndex = i;
        }
    }
    
    cout << targetIndex << "\n";
    return 0;
}

Problema B - AtCoder Amusement Park

Devemos alocar grupos de amigos em atrações que possuem uma restrição máxima de capacidade K. A solução consiste em simular o processo de alocação: mantemos um contador da ocupação atual da atração. Ao adicionar um novo grupo, se a capacidade for excedida, incrementamos o número de atrações necessárias e reiniciamos a ocupação com o tamanho do grupo atual.

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int numGroups, maxCapacity;
    cin >> numGroups >> maxCapacity;
    
    int attractionsUsed = 1;
    int currentOccupancy = 0;
    
    for (int i = 0; i < numGroups; ++i) {
        int groupSize;
        cin >> groupSize;
        
        if (currentOccupancy + groupSize <= maxCapacity) {
            currentOccupancy += groupSize;
        } else {
            attractionsUsed++;
            currentOccupancy = groupSize;
        }
    }
    
    cout << attractionsUsed << "\n";
    return 0;
}

Problema C - Sigma Problem

Para calcular o somatório de (A_i + A_j) % 10^8 para todos os pares, podemos inicialmenet assumir que não há restrição de módulo. Nesse cenário, cada elemento é somado N - 1 vezes. Para corrigir o valor e aplicar o módulo, ordenamos o array e utilizamos a técnica de dois ponteiros. Para cada elemento à direita, contamos quantos elementos à esquerda formam uma soma maior ou igual a 10^8, subtraindo o excesso correspondente do total acumulado.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<long long> values(n);
    long long totalSum = 0;
    const long long MOD_VAL = 100000000LL;
    
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
        totalSum += values[i] * (n - 1);
    }
    
    sort(values.begin(), values.end());
    
    int leftPtr = 0;
    long long penalty = 0;
    
    for (int right = 0; right < n; ++right) {
        while (leftPtr < right && values[leftPtr] + values[right] >= MOD_VAL) {
            leftPtr++;
        }
        penalty += leftPtr;
    }
    
    cout << totalSum - (penalty * MOD_VAL) << "\n";
    return 0;
}

Problema D - Another Sigma Problem

A concatenação de dois números A e B equivale matematicamente a A * 10^(len(B)) + B. A estratégia envolve manter um mapa de frequências com o comprimento das strings de cada número. Ao iterar pelo array, calculamos a contribuição de cada elemento atuando tanto como a parte direita (multiplicado pelo número de elementos anteriores) quanto como a parte esquerda (multiplicado por potências de 10 baseadas nos comprimentos dos elementos subsequentes).

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

using namespace std;

const long long MOD = 998244353;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<long long> sequence(n);
    map<int, int> lengthCounts;
    
    for (int i = 0; i < n; ++i) {
        cin >> sequence[i];
        lengthCounts[to_string(sequence[i]).length()]++;
    }
    
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        total = (total + sequence[i] * i) % MOD;
        
        int currentLen = to_string(sequence[i]).length();
        lengthCounts[currentLen]--;
        
        for (auto const& [len, count] : lengthCounts) {
            if (count > 0) {
                long long multiplier = power(10, len);
                long long contribution = (sequence[i] * multiplier) % MOD;
                contribution = (contribution * count) % MOD;
                total = (total + contribution) % MOD;
            }
        }
    }
    
    cout << total << "\n";
    return 0;
}

Problema E - Yet Another Sigma Problem

Para determinar a soma dos prefixos comuns mais longos (LCP) entre todos os pares de strings, empregamos uma estrutura de dados Trie. Durante a inserção de cada palavra, incrementamos um contador em cada nó visitado. A contribuição total de um nó específico para o resultado final é dada pela combinação de strings que compartilham aquele prefixo, calculada através da fórmula C * (C - 1) / 2, onde C é a frequência de passagem pelo nó.

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

using namespace std;

struct TrieNode {
    int passCount;
    int children[26];
    TrieNode() {
        passCount = 0;
        fill(begin(children), end(children), 0);
    }
};

const int MAX_NODES = 1000005;
TrieNode trie[MAX_NODES];
int nodeCounter = 0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        string word;
        cin >> word;
        int current = 0;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!trie[current].children[idx]) {
                trie[current].children[idx] = ++nodeCounter;
            }
            current = trie[current].children[idx];
            trie[current].passCount++;
        }
    }
    
    long long totalLCP = 0;
    for (int i = 1; i <= nodeCounter; ++i) {
        long long c = trie[i].passCount;
        totalLCP += c * (c - 1) / 2;
    }
    
    cout << totalLCP << "\n";
    return 0;
}

Problema F - Tile Distance

A mecânica de movimentação neste grid varia de acordo com o parâmetro K. Para K=1, a solução é a tradicional distância de Manhattan. Quando K=2, o custo de transição entre blocos exige uma fórmula ajustada. Para K >= 3, a rota diagonal torna-se a mais eficiente; modelamos isso rotacionando o sistema de coordenadas em 45 graus. O algoritmo avalia o custo mínimo para alcançar um bloco em formato de L a partir das posições inicial e final, combinando esses custos com a distância entre os próprios blocos.

#include <iostream>
#include <vector>
#include <array>
#include <cmath>
#include <algorithm>

using namespace std;

vector<array<long long, 3>> getAdjacentBlocks(long long x, long long y, long long k) {
    x += k; 
    y += k;
    vector<array<long long, 3>> blocks;
    
    if (((x / k) + (y / k)) % 2 != 0) {
        blocks.push_back({x / k, y / k, 0});
        return blocks;
    }
    
    blocks.push_back({x / k, y / k + 1, k - (y % k)});
    blocks.push_back({x / k, y / k - 1, (y % k) + 1});
    blocks.push_back({x / k - 1, y / k, (x % k) + 1});
    blocks.push_back({x / k + 1, y / k, k - (x % k)});
    
    return blocks;
}

long long calculateBlockDistance(long long x1, long long y1, long long x2, long long y2, long long k) {
    long long dx = abs(x1 - x2);
    long long dy = abs(y1 - y2);
    
    if (k == 2) {
        return dx + dy + abs(dx - dy) / 2;
    }
    
    long long rx1 = x1 + y1, ry1 = y1 - x1;
    long long rx2 = x2 + y2, ry2 = y2 - x2;
    
    return abs(rx1 - rx2) + abs(ry1 - ry2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long k, sx, sy, tx, ty;
    cin >> k >> sx >> sy >> tx >> ty;
    
    long long minCost = abs(sx - tx) + abs(sy - ty);
    
    if (k == 1) {
        cout << minCost << "\n";
        return 0;
    }
    
    auto startBlocks = getAdjacentBlocks(sx, sy, k);
    auto targetBlocks = getAdjacentBlocks(tx, ty, k);
    
    for (const auto& start : startBlocks) {
        for (const auto& target : targetBlocks) {
            long long currentCost = start[2] + target[2] + 
                calculateBlockDistance(start[0], start[1], target[0], target[1], k);
            minCost = min(minCost, currentCost);
        }
    }
    
    cout << minCost << "\n";
    return 0;
}