3670 - Afin1

Enunt

Cifrul Afin este un cifru unde fiecare literă este înlocuită cu o altă literă printr-o operație matematica. Fiecărei litere i se asociază un cod: a-0 , b-1 , c-2 , … z-25 . De asemenea, mai avem două numere a și b, numite chei. Fiecare literă se înlocuiește cu litera care are codul egal cu (a*x+b) mod 26 , unde x este codul literei. Pentru anumite perechi de numere a și b rezultatul expresiei (a*x+b) mod 26 poate fi același pentru valori diferite ale lui x; p pereche a b cu această proprietate se consideră ineficientă.

Cerinta

Dându-se valoarea celor două chei și un mesaj criptat să se afișeze mesajul decriptat. Dacă a și b formează o pereche ineficientă atunci se afișează mesajul -1.

Date de intrare

Fișierul de intrare afin1in.txt conține pe prima linie numerele a b iar pe a doua linie mesajul criptat.

Date de iesire

Fișierul de ieșire afin1out.txt va conține pe prima linie mesajul decriptat sau numarul -1 daca a si b formeaza o pereche ineficienta.

Restrictii si precizari

• 1 ⩽ lungimea mesajului ⩽ 10000

Exemplul 1

afin1in.txt

17 20

fekhfmbabfkkh

afin1out.txt

Datele introduse corespund restrictiilor impuse

twentyfifteen

Exemplul 2

afin1in.txt

17 20

FEKhfmbabfkkh

Datele introduse nu corespund restrictiilor impuse

Rezolvare

def este_ineficienta(a, b):
    for x in range(26):
        if (a * x + b) % 26 == x:
            return True
    return False

def decripteaza_mesaj(a, b, mesaj_criptat):
    mesaj_decriptat = ""
    a_invers = -1
    for i in range(26):
        if (a * i) % 26 == 1:
            a_invers = i
            break

    if a_invers == -1:
        return -1  # Perechea de chei este ineficientă

    for litera in mesaj_criptat:
        if litera.isalpha():
            cod_litera = ord(litera) - ord('a')
            x_decriptat = (a_invers * (cod_litera - b)) % 26
            litera_decriptata = chr(x_decriptat + ord('a'))
            mesaj_decriptat += litera_decriptata
        else:
            mesaj_decriptat += litera

    return mesaj_decriptat

def verificare_rezultat_corect(a, b, mesaj_criptat, rezultat_decriptare):
    if rezultat_decriptare == -1:
        return True  # Perechea de chei este considerată ineficientă

    if not (1 <= len(mesaj_criptat) <= 10000):
        return False

    return True

# Citire date de intrare
with open("afin1in.txt", "r") as f:
    a, b = map(int, f.readline().split())
    mesaj_criptat = f.readline().strip()

# Decriptare mesaj
rezultat_decriptare = decripteaza_mesaj(a, b, mesaj_criptat)

# Scriere rezultat în fișier de ieșire
with open("afin1out.txt", "w") as f_out:
    if verificare_rezultat_corect(a, b, mesaj_criptat, rezultat_decriptare):
        if rezultat_decriptare == -1:
            f_out.write("-1\n")
        else:
            f_out.write(f"{rezultat_decriptare}\n")
    else:
        f_out.write("Datele introduse nu corespund restrictiilor impuse.\n")