Problema 1: Classificador de Força de Senha

Na criação de senhas para diversos serviços online, é crucial assegurar a segurança. Para avaliar a robustez de uma senha, pode-se empregar um "classificador de strings" que a divide em quatro categorias distintas, mantendo a ordem relativa dos caracteres originais:

• Caracteres minúsculos (a-z)
• Caracteres maiúsculos (A-Z)
• Dígitos numéricos (0-9)
• Caracteres especiais ou outros símbolos

Por exemplo, a senha "1q2w3E4R5{6}" seria decomposta nas seguintes partes: "qw", "ER", "123456", e "{}".

A força da senha é determinada pelo número de categorias não vazias. O nível mínimo é 1 (se pelo menos uma categoria não for nula) e o máximo é 4 (se todas as quatro categorias contiverem caracteres). Por exemplo, "asdA@123" tem nível 4, enquanto "20020101" tem nível 1.

Abordagem da Solução

Este problema pode ser resolvido com uma abordagem direta, iterando sobre a string de entrada e categorizando cada caractere. O objetivo é simular o processo de classificação e contar as categorias preenchidas.

Implementação em C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // Para std::count_if

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::string senha_entrada;
    std::cin >> senha_entrada;

    std::vector<std::string> segmentos(4); // 0:minúsculas, 1:maiúsculas, 2:dígitos, 3:especiais

    for (char caractere : senha_entrada) {
        if (caractere >= 'a' && caractere <= 'z') {
            segmentos[0] += caractere;
        } else if (caractere >= 'A' && caractere <= 'Z') {
            segmentos[1] += caractere;
        } else if (caractere >= '0' && caractere <= '9') {
            segmentos[2] += caractere;
        } else {
            segmentos[3] += caractere;
        }
    }

    int nivel_seguranca = 0;
    for (int i = 0; i < 4; ++i) {
        if (!segmentos[i].empty()) {
            nivel_seguranca++;
        } else {
            segmentos[i] = "(Nulo)"; // Representação para segmentos vazios
        }
    }

    std::cout << "Nivel da senha: " << nivel_seguranca << "\n";
    for (int i = 0; i < 4; ++i) {
        std::cout << segmentos[i] << "\n";
    }

    return 0;
}

Problema 2: Otimização de Saltos em uma Sequência

Este problema envolve encontrar o número mínimo de "saltos mágicos" necessários para atravessar uma sequência de pontos, otimizando o caminho com base nas capacidades de salto em cada ponto e priorizando o menor índice possível para o salto mágico quando múltiplas opções existem.

A tarefa é simular um processo de travessia unidirecional (sem retroceder), onde, em cada passo, se busca alcançar o ponto mais distante possível. Se o ponto atual é o limite do que pode ser alcançado sem um salto mágico, um salto mágico deve ser usado. O salto mágico é sempre feito a partir do ponto que permitiu alcançar o maior alcance máximo até aquele momento, e entre as opções que dão o mesmo alcance, escolhe-se o de menor índice. O objetivo é determinar a quantidade de saltos mágicos e a posição de cada um.

Abordagem da Solução

Uma abordagem gulosa é eficaz para este problema. A ideia central é sempre avançar o máximo possível. Mantemos o ponto mais distante que podemos alcançar (alcance_maximo) e o ponto inicial mais à esquerda (origem_salto_magico) que nos permite atingir esse alcance_maximo. Conforme percorremos a sequência, se o ponto atual é o limite do nosso alcance_maximo (sem usar um salto mágico adicional), então devemos ativar um salto mágico a partir da origem_salto_magico para estender nosso alcance. O alcance_maximo é então atualizado para a próxima posição, e a origem_salto_magico também é resetada para a próxima posição. A travessia termina quando o alcance_maximo excede o último ponto da sequência.

Implementação em C++

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

const int MAX_PONTOS = 1e5 + 10;
int capacidades_salto[MAX_PONTOS]; // Capacidade de salto em cada ponto

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n_pontos;
    std::cin >> n_pontos;

    for (int i = 1; i <= n_pontos; ++i) {
        std::cin >> capacidades_salto[i];
    }

    int num_saltos_magicos = 0;
    int indice_proximo_salto = 1; // Ponto inicial da próxima "seção" de saltos normais
    int maior_alcance_atual = 1; // Alcance máximo que podemos atingir a partir de indice_proximo_salto
    int ponto_para_magia = 1; // O ponto mais à esquerda que nos permitiu atingir o maior_alcance_atual

    std::vector<int> posicoes_saltos_magicos; // Armazena as posições onde os saltos mágicos foram usados

    for (int i = 1; i <= n_pontos; ++i) {
        // Se houver capacidade de salto neste ponto 'i'
        if (capacidades_salto[i] > 0) {
            // Se o salto a partir de 'i' alcança mais longe do que o maior_alcance_atual registrado
            if (i + capacidades_salto[i] > maior_alcance_atual) {
                maior_alcance_atual = i + capacidades_salto[i]; // Atualiza o alcance máximo
                ponto_para_magia = i; // Registra 'i' como o melhor ponto para um salto mágico (o mais à esquerda)
            }
        }
        
        // Se chegamos ao limite do nosso alcance sem usar um salto mágico
        if (maior_alcance_atual == i) {
            // Precisamos de um salto mágico. O salto será feito de ponto_para_magia.
            posicoes_saltos_magicos.push_back(ponto_para_magia);
            
            // O novo alcance máximo é apenas o próximo ponto (como se tivéssemos "pulado" sobre 'i')
            maior_alcance_atual = i + 1;
            // O próximo ponto de onde poderíamos lançar um novo salto mágico é também 'i + 1'
            ponto_para_magia = i + 1;
        }

        // Se já alcançamos ou ultrapassamos o final da sequência, podemos parar
        if (maior_alcance_atual > n_pontos) {
            break;
        }
    }

    std::cout << posicoes_saltos_magicos.size() << "\n";
    for (size_t i = 0; i < posicoes_saltos_magicos.size(); ++i) {
        std::cout << posicoes_saltos_magicos[i] << (i == posicoes_saltos_magicos.size() - 1 ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}