Problemi 094

Kërkesa

Në grupin e programimit ne kemi qejf ti dërgojmë njëri tjetrit panagrama. Një fjali ose shprehje quhet panagram kur i përmban të gjitha shkronjat e alfabetit anglisht të paktën një herë. P.sh. shprehja “the quick brown fox jumps over the lazy dog” është një panagram. Ndonjëherë panagramat tona përmbajnë informata sekrete, si p.sh. “CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS”, dhe duhen mbajtur të fshehta.

Pasi lexuam për disa minuta një libër rreth shifrimit(enkriptimit), dhe mësuam se është shumë e vështirë të gjenden përbërësit e prodhimit të dy numrave të thjeshtë shumë të mëdhenj, hartuam një skemë shifrimi të bazuar në këtë fakt. Fillimisht bëmë këto përgatitje:

• Zgjodhëm 26 numra të thjeshtë të ndryshëm nga njëri tjetri dhe më të vegjël se N.
• I renditëm nga më i vogli te më i madhi. Pastaj më të voglit i caktuam shkronjën A, të dytit shkronjën B, e kështu me radhë.
• Të gjithë pjesëtarët e grupit e mbajtën shënim këtë listë.

Tani, kur duam të dërgojmë ndonjë panagram si mesazh, fillimisht heqim të gjitha vendet bosh midis fjalëve, pastaj shkruajmë prodhimin e numrave të thjeshtë që i korrespondojnë shkronjës së parë dhe të dytë të mesazhit, pastaj shkruajmë prodhimin e numrave të thjeshtë të shkronjës së dytë dhe të tretë, e kështu me radhë, duke përfunduar me prodhimin e numrave të shkronjës së fundit dhe të parafundit. Kjo listë me numra që formohet është versioni i shifruar i mesazhit.

P.sh. nqs N=103 dhe kemi zgjedhur të përdorim 26 numrat e parë të thjeshtë pas numrit 2 (sepse kemi frikë se faktorizimi i numrave çift është shumë i thjeshtë), do kemi A=3, B=5, C=7, D=11, e kështu me radhë, deri te Z=103. Nqs duam të kriptojmë panagramën “CJ QUIZ…” më sipër, teksti do jetë “CJQUIZKNOWBEVYOFDPFLUXALGORITHMS”. Atere numri i parë i mesazhit të shifruar do jetë 7*31=217 (sepse C=7 dhe J=31), numri i dytë do jetë 1891, e kështu me radhë, numri i fundit do jetë 3053.

Nëse ju jepet një mesazh i shifruar në këtë mënyrë dhe numri N i përdorur, por pa ju thënë se cilët numra të thjeshtë janë përdorur, a mund ta deshifroni atë dhe të gjeni mesazhin origjinal.

Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/000000000008830b

Shembull

$ cat input.txt
2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543

$ python3 prog.py < input.txt
Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ

Për çdo rast testimi jepen numrat N dhe L, ku N është kufiri i numrave të thjeshtë të përdorur, dhe L është gjatësia e listës me prodhimet e numrave të thjeshtë, e cila jepet në rreshtin pasardhës.

Zgjidhja

from math import gcd
for t in range(int(input())):
    N, L = map(int, input().split())
    C = [int(i) for i in input().split()]    # ciphertext

    # find prime numbers comprising the original message
    S = [0]*(L + 1)
    i = 0
    while C[i] == C[i+1]:
        i += 1
    S[i+1] = gcd(C[i], C[i+1])
    j = i
    while j >= 0:
        S[j] = C[j] // S[j+1]
        j -= 1
    i += 1
    while i < L:
        S[i+1] = C[i] // S[i]
        i += 1

    # find the mapping between the prime numbers and the letters of the aplhabet
    A = list(set(S))
    A.sort()
    M = {}    # mapping
    for i in range(len(A)):
        M[A[i]] = chr(ord('A') + i)

    # find the original deciphered message
    msg = ''.join([M[i] for i in S])

    print('Case #{}: {}'.format(t+1, msg))

Sqarime

Le të shënojmë me Prime(X) numrin e thjeshtë që i korrespondon shkronjës X, dhe le të jenë XYZ tre shkronja të njëpasnjëshme në mesazhin e pa shifruar. Atere në listën e numrave të dhënë do kemi dy numra të njëpasnjëshëm L1=Prime(X)Prime(Y) dhe L2=Prime(Y)Prime(Z). Mund të vëmë re se Prime(Y) është pjesëtuesi më i madh i përbashkët i numrave të njëpasnjëshëm L1 dhe L2, dhe PMP i dy numrave mund të gjendet shumë lehtë (me algoritmin e Euklidit). Pasi kemi gjetur Prime(Y)=PMP(L1, L2), mund të gjejmë shumë kollaj edhe Prime(X)=L1/Prime(Y) dhe Prime(Z)=L2/Prime(Y).

Duke përdorur këtë metodë mund të gjejmë të gjithë numrat e thjeshtë që janë përdorur në mesazh, dhe meqenëse mesazhi i dhënë është panagram dhe aty ndodhen të 26 shkronjat e alfabetit (anglisht), do na dalin 26 numra të thjeshtë. Mund ti rendisim këta numra dhe të parin ta vëmë në korrespondencë me shkronjën A, të dytin me shkronjën B, e kështu me radhë. Duke ditur këtë korrespondence dhe numrat e thjeshtë që përbëjnë mesazhin, mund të gjejmë shkronjat e mesazhit fillestar.

Shënim: Nqs mesazhi fillestar fillon me shkronja që përsëriten, si p.sh. ABABAB… atere numrat e parë të mesazhit të shifruar do jenë të barabartë: Prime(A)Prime(B) dhe Prime(B)Prime(A), dhe kështu që PMP e tyre do jetë 0. Kështu që zbërthimin me PMP duhet ta fillojmë aty ku kemi dy numra të njëpasnjëshëm që janë të ndryshëm.

Detyra

Jepet një numër n. Gjeni mbetjen e pjesëtimit të shumës \(1! + 2! + ... + n!\) me \(10^9 + 7\) (i cili është numër i thjeshtë).

Referenca: https://www.codechef.com/DARG2019/problems/SUMMOD

Shembull

$ cat input.txt
3
1000
10000
100000

$ python3 prog.py < input.txt
980630010
396626132
789934569