"""
Módulo de Simulação de Caixa Eletrônico (Saque)

Este script simula a lógica de um caixa eletrônico para saques em dinheiro. 
Ele recebe um valor do usuário, valida a entrada e calcula a menor 
quantidade possível de cédulas para compor o valor desejado usando 
um algoritmo de Programação Dinâmica (semelhante ao "Coin Change Problem").
"""

# Constantes de configuração do caixa eletrônico
CEDULAS = (100, 50, 20, 10, 5, 2)  # Cédulas disponíveis no caixa
LIMITE_SAQUE = 20_000              # Valor máximo permitido por saque
MAX_TENTATIVAS = 3                 # Número máximo de tentativas de entrada inválida


def formatar_reais(valor):
    """
    Formata um valor inteiro para o padrão de moeda brasileiro (Real).
    
    Args:
        valor (int): O valor numérico a ser formatado.
        
    Returns:
        str: String formatada (ex: 1500 -> "R$ 1.500,00").
    """
    return f"R$ {valor:,}".replace(",", ".") + ",00"


def calcular_cedulas(valor):
    """
    Calcula a menor quantidade de cédulas necessárias para um dado valor.
    
    Utiliza Programação Dinâmica para testar as combinações possíveis.
    Como não há cédula de R$ 1, alguns valores (ex: 1, 3) são impossíveis.
    
    Args:
        valor (int): O valor desejado para o saque.
        
    Returns:
        dict: Um dicionário onde as chaves são os valores das cédulas 
              e os valores são as quantidades necessárias.
        None: Se for impossível compor o valor com as cédulas disponíveis.
    """
    # minimo[i] guardará a quantidade mínima de cédulas para o valor 'i'.
    # Inicializado com infinito, pois ainda não sabemos a quantidade.
    minimo = [float("inf")] * (valor + 1)
    
    # ultima_cedula[i] guardará o valor da última cédula adicionada para formar o valor 'i'.
    ultima_cedula = [0] * (valor + 1)
    
    # Para o valor 0, precisamos de 0 cédulas.
    minimo[0] = 0

    # Constrói a solução de baixo para cima (bottom-up)
    for total in range(1, valor + 1):
        for cedula in CEDULAS:
            if cedula <= total:
                # Quantidade se usarmos esta cédula + o que já calculamos para o restante
                quantidade = minimo[total - cedula] + 1

                # Se for a melhor (menor) quantidade encontrada até agora, atualizamos
                if quantidade < minimo[total]:
                    minimo[total] = quantidade
                    ultima_cedula[total] = cedula

    # Se o valor final continuou infinito, não há combinação possível
    if minimo[valor] == float("inf"):
        return None

    # Reconstrói a solução a partir do array ultima_cedula
    resultado = {}
    restante = valor

    while restante:
        cedula = ultima_cedula[restante]
        resultado[cedula] = resultado.get(cedula, 0) + 1
        restante -= cedula

    return resultado


def validar_saque(entrada):
    """
    Valida a entrada do usuário e tenta processar o pedido de saque.
    
    Args:
        entrada (str): O input bruto digitado pelo usuário.
        
    Returns:
        tuple: Retorna uma tupla contendo (valor, quantidades, erro):
            - valor (int ou None): O valor convertido para inteiro (se válido).
            - quantidades (dict ou None): Dicionário com as cédulas.
            - erro (str ou None): Mensagem de erro caso a validação falhe.
    """
    entrada = entrada.strip()

    # Validação básica de tipo e formato (evita letras, símbolos, decimais ou números negativos)
    if not entrada or not entrada.isascii() or not entrada.isdigit():
        return None, None, "Formato inválido. Digite apenas números inteiros."

    # Remove zeros à esquerda. Se ficar vazio, assume "0"
    entrada = entrada.lstrip("0") or "0"
    limite = str(LIMITE_SAQUE)

    # Validação de limite via strings (evita estourar memória ou lentidão 
    # se o usuário digitar uma string de milhares de dígitos)
    if (
        len(entrada) > len(limite)
        or (len(entrada) == len(limite) and entrada > limite)
    ):
        return None, None, (
            f"Saque negado. Para valores acima de "
            f"{formatar_reais(LIMITE_SAQUE)}, "
            "realize o saque no caixa interno."
        )

    valor = int(entrada)

    if valor == 0:
        return None, None, "O valor deve ser maior que zero."

    # Se chegou aqui, a entrada é válida. Tenta calcular as cédulas.
    quantidades = calcular_cedulas(valor)

    # Verifica se o algoritmo de PD encontrou uma combinação válida
    if quantidades is None:
        return None, None, (
            "Não é possível sacar esse valor com as cédulas disponíveis."
        )

    return valor, quantidades, None


def main():
    """
    Função principal que gerencia o fluxo de interação com o usuário.
    Gerencia as tentativas, exibe os resultados no terminal e trata 
    interrupções inesperadas (como Ctrl+C).
    """
    for tentativa in range(1, MAX_TENTATIVAS + 1):
        try:
            entrada = input(
                "\nDigite o valor do saque em reais inteiros (ex.: 1500): "
            )
        except (EOFError, KeyboardInterrupt):
            # Captura se o usuário fechar o terminal abruptamente ou usar Ctrl+C
            print("\nOperação cancelada.")
            return

        # Chama a validação e processamento
        valor, quantidades, erro = validar_saque(entrada)

        # Se não houver erro, a transação foi aprovada
        if erro is None:
            print("\nQuantidade de cédulas:")

            # Imprime as cédulas ordenadas da maior para a menor
            for cedula in sorted(quantidades, reverse=True):
                print(
                    f"{quantidades[cedula]} cédula(s) "
                    f"de {formatar_reais(cedula)}"
                )

            print(f"\nTotal do saque: {formatar_reais(valor)}")
            print("Valor restante: R$ 0,00")
            return

        # Caso haja erro de validação, imprime a mensagem
        print(erro)

        # Informa quantas tentativas ainda restam antes do bloqueio
        restantes = MAX_TENTATIVAS - tentativa
        if restantes:
            print(f"Tentativas restantes: {restantes}")

    # Atingiu o número máximo de tentativas
    print(
        "\nPor motivo de segurança, a operação será abortada. "
        "Você deverá tentar de novo."
    )


if __name__ == "__main__":
    main()