Problema A - Long Loong

Neste desafio, o objetivo é construir uma string que começa com "L", contém um número variável de letras "o" definido pela entrada N e termina com "ng". Uma abordagem direta utilizando um laço de repetição é suficiente para resolver o problema.

#include <iostream>
#include <string>

using namespace std;

void executar_a() {
    int repeticoes;
    if (!(cin >> repeticoes)) return;
    
    string resultado = "L";
    for (int i = 0; i < repeticoes; ++i) {
        resultado += 'o';
    }
    resultado += "ng";
    cout << resultado << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    executar_a();
    return 0;
}

Problema B - CTZ (Count Trailing Zeros)

O problema solicita a contagem de zeros consecutivos à direita na representação binária de um número inteiro. Isso pode ser resolvido através de operações de deslocamento de bits (bit shifting) e verificação do bit menos significativo.

#include <iostream>

using namespace std;

void calcular_zeros_finais() {
    int valor;
    cin >> valor;
    
    int contador = 0;
    while (valor > 0 && (valor & 1) == 0) {
        contador++;
        valor >>= 1;
    }
    cout << contador << endl;
}

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

Problema C - Even Digits

O desafio pede para encontrar o N-ésimo número (começando do zero) que contém apenas dígitos pares (0, 2, 4, 6, 8). Note que existem exatamente 5 dígitos disponíveis. Isso caracteriza um sistema de numeração de base 5, onde cada dígito deve ser multiplicado por 2 para obter o valor correspondente no conjunto de dígitos pares.

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

using namespace std;

typedef long long ll;

void resolver_digitos_pares() {
    ll n;
    cin >> n;
    n--; // Ajuste para indexação zero
    
    if (n == 0) {
        cout << 0 << endl;
        return;
    }
    
    vector<int> digitos;
    while (n > 0) {
        digitos.push_back((n % 5) * 2);
        n /= 5;
    }
    
    reverse(digitos.begin(), digitos.end());
    for (int d : digitos) cout << d;
    cout << endl;
}

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

Problema D - Pyramid

Para formar uma pirâmide de altura k centralizada na posição i, os elementos ao redor devem suportar uma sequência crescente e decrescente (ex: 1, 2, 3, 2, 1). A altura máxima possível em cada posição i é limitada pelo próprio valor A[i] e pela capacidade dos vizinhos à esquerda e à direita de manterem a prgoressão.

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

using namespace std;

void calcular_piramide_maxima() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    vector<int> esquerda(n + 2, 0), direita(n + 2, 0);
    
    for (int i = 1; i <= n; ++i) {
        esquerda[i] = min(a[i], esquerda[i - 1] + 1);
    }
    
    for (int i = n; i >= 1; --i) {
        direita[i] = min(a[i], direita[i + 1] + 1);
    }
    
    int max_altura = 0;
    for (int i = 1; i <= n; ++i) {
        max_altura = max(max_altura, min(esquerda[i], direita[i]));
    }
    cout << max_altura << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    calcular_piramide_maxima();
    return 0;
}

Problema E - Digit Sum Divisible

Este problema requer contar números x <= N tais que x seja divisível pela soma de seus próprios dígitos. Como a soma máxima dos dígitos para N = 10^14 é relativamente pequena (9 * 14 = 126), podemos iterar sobre todas as somas possíveis S e usar Programação Dinâmica em Dígitos para contar quantos números têm soma de dígitos igual a S e resto zero quando divididos por S.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long ll;

ll memo[16][150][150][2];
int digitos_n[16];
int limite_soma;

ll dp_digitos(int pos, int soma_atual, int resto, bool restrito) {
    if (soma_atual > limite_soma) return 0;
    if (pos < 0) return (soma_atual == limite_soma && resto == 0);
    
    if (memo[pos][soma_atual][resto][restrito] != -1)
        return memo[pos][soma_atual][resto][restrito];
        
    ll total = 0;
    int limite = restrito ? digitos_n[pos] : 9;
    
    for (int d = 0; d <= limite; ++d) {
        total += dp_digitos(pos - 1, 
                            soma_atual + d, 
                            (resto * 10 + d) % limite_soma, 
                            restrito && (d == limite));
    }
    
    return memo[pos][soma_atual][resto][restrito] = total;
}

void resolver_dp_digitos() {
    ll n;
    cin >> n;
    string s = to_string(n);
    int tam = s.size();
    for (int i = 0; i < tam; ++i) {
        digitos_n[i] = s[tam - 1 - i] - '0';
    }
    
    ll resposta_final = 0;
    int soma_maxima = tam * 9;
    
    for (int s_alvo = 1; s_alvo <= soma_maxima; ++s_alvo) {
        limite_soma = s_alvo;
        memset(memo, -1, sizeof(memo));
        resposta_final += dp_digitos(tam - 1, 0, 0, true);
    }
    
    cout << resposta_final << endl;
}

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