T1 - Verificação de Par ou Ímpar

Dado um número inteiro n, se n for par, imprima "even"; se for ímpar, imprima "odd".

Entrada: Um único inteiro n.

Saída: Uma string representando a paridade.

Faixa de dados: -1.000.000 ≤ n ≤ 1.000.000

Exemplo: Entrada: 0 Saída: even

Solução: A paridade é determinada usando o operador módulo. Para inteiros negativos, n % 2 pode ser -1, então verificamos se é zero.

#include <iostream>
using namespace std;

int main() {
    int valor;
    cin >> valor;
    bool ehPar = (valor % 2 == 0);
    if (ehPar) {
        cout << "even" << endl;
    } else {
        cout << "odd" << endl;
    }
    return 0;
}

T2 - Construção de Pirâmide com Blocos

Uma pirâmide tem a primeira camada com 1 bloco, a segunda com 2 blocos, e assim por diante. Dado n blocos, determine o número máximo de camadas que podem ser construídas.

Entrada: Um enteiro positivo n.

Saída: Um inteiro representando o máximo de camadas.

Faixa de dados: 1 ≤ n ≤ 1.000.000.000

Exemplo: Entrada: 12 Saída: 4

Solução: O total de blocos para k camadas é k*(k+1)/2. Podemos resolver iterativamente.

#include <iostream>
using namespace std;

int main() {
    long long totalBlocos;
    cin >> totalBlocos;
    int camadas = 0;
    long long acumulado = 0;
    while (acumulado + camadas + 1 <= totalBlocos) {
        camadas++;
        acumulado += camadas;
    }
    cout << camadas << endl;
    return 0;
}

T3 - Plataforma Mais Longa

Dada uma sequência de inteiros, encontre a maior plataforma (sequência contínua de números iguais) e conte quantas existem.

Entrada: Primeiro linha um inteiro n; segunda linha n inteiros.

Saída: Dois inteiros: comprimento da maior plataforma e sua contagem.

Faixa de dados: n ≤ 500.000, 1 ≤ a_i ≤ 1.000.000

Exemplo: Entrada: 7 2 2 2 1 3 3 3 Saída: 3 2

Solução: Percorra a sequência, mantendo um comprimento atual e atualizando o máximo.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int tamanho;
    cin >> tamanho;
    vector<int> dados(tamanho);
    for (int i = 0; i < tamanho; i++) {
        cin >> dados[i];
    }
    int maxComprimento = 0;
    int contador = 0;
    int comprimentoAtual = 1;
    for (int i = 1; i < tamanho; i++) {
        if (dados[i] == dados[i-1]) {
            comprimentoAtual++;
        } else {
            if (comprimentoAtual > maxComprimento) {
                maxComprimento = comprimentoAtual;
                contador = 1;
            } else if (comprimentoAtual == maxComprimento) {
                contador++;
            }
            comprimentoAtual = 1;
        }
    }
    if (comprimentoAtual > maxComprimento) {
        maxComprimento = comprimentoAtual;
        contador = 1;
    } else if (comprimentoAtual == maxComprimento) {
        contador++;
    }
    cout << maxComprimento << " " << contador << endl;
    return 0;
}

T4 - Coloração de Blocos

Dado n blocos e m cores, conte as maneiras de colorir os blocos de modo que blocos adjacentes tenham cores diferentes, modulo 10^9+7.

Entrada: Dois inteiros n e m.

Saída: O número de esquemas modulo 10^9+7.

Faixa de dados: 1 ≤ n ≤ 10^15, 1 ≤ m ≤ 10^9

Exemplo: Entrada: 3 2 Saída: 2

Solução: O primeiro bloco tem m opções, os subsequentes têm m-1 opções cada. Use exponenciação modular para grandes n.

#include <iostream>
using namespace std;

const int MODULO = 1e9 + 7;

long long exponenciacaoModular(long long base, long long expoente) {
    long long resultado = 1;
    base %= MODULO;
    while (expoente > 0) {
        if (expoente % 2 == 1) {
            resultado = (resultado * base) % MODULO;
        }
        base = (base * base) % MODULO;
        expoente /= 2;
    }
    return resultado;
}

int main() {
    long long n, m;
    cin >> n >> m;
    long long res = m * exponenciacaoModular(m - 1, n - 1) % MODULO;
    cout << res << endl;
    return 0;
}

T5 - Sequência de Saída de Pilha Léxicograficamente Mínima

Dada uma string de entrada que é empilhada sequencialmente, encontre a sequência de saída de pilha com a menor ordem lexicográfica.

Entrada: Primeiro linha um inteiro n; segunda linha uma string de tamanho n.

Saída: A string representando a sequência de saída mínima.

Faixa de dados: 1 ≤ n ≤ 10^5

Exemplo: Entrada: 3 yes Saída: esy

Solução: Use uma pilha e um array de mínimos sufixos para decidir quando empilhar ou desempilhar.

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int main() {
    int tamanho;
    cin >> tamanho;
    string entrada;
    cin >> entrada;
    vector<char> minimoSufixo(tamanho);
    minimoSufixo[tamanho-1] = entrada[tamanho-1];
    for (int i = tamanho-2; i >= 0; i--) {
        minimoSufixo[i] = min(entrada[i], minimoSufixo[i+1]);
    }
    stack<char> pilha;
    string saida;
    int indice = 0;
    for (int i = 0; i < tamanho; i++) {
        while (!pilha.empty() && pilha.top() <= minimoSufixo[i]) {
            saida += pilha.top();
            pilha.pop();
        }
        pilha.push(entrada[i]);
    }
    while (!pilha.empty()) {
        saida += pilha.top();
        pilha.pop();
    }
    cout << saida << endl;
    return 0;
}