0631 - Passwd

Enunț

Alexandru dorește să devină expert în securitate, iar pentru aceasta s-a apucat să învete mai multe despre siguranța parolelor. El dorește să afle câte parole poate crea folosind a litere mici ale alfabetului englez și b litere mari ale alfabetului englez, c cifre si d caractere din mulțimea {!, @, #, $, %}. Totodată, el vrea să găsească parola cu numărul x în ordine lexicografică, formată din caracterele descrise mai sus.

Cerința

Cunoscând a, b, c, d si x se cere:

a) A x-a parolă în ordine lexicografică, formată din caracterele menționate în enunț.

b) Numărul de parole diferite formate din caracterele menționate în enunț, modulo 666013.

Date de intrare

Fişierul de intrare passwdIN.txt conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe a doua linie se găsesc patru numere naturale a, b, c și d cu semnificația din enunț, separate prin câte un spațiu. A treia linie conține un singur număr natural x, cu semnificația din enunț.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință.

În acest caz, în fişierul de ieşire passwdOUt.txt se va scrie parola cu numărul x în ordine lexicografică, descrisă în enunț.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință.

În acest caz, în fişierul de ieşire passwdOUt.txt se va scrie numărul de parole distincte, formate cu caracterele descrise în enunț, modulo 666013.

În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ a, b, c, d ≤ 2500
• 1 ≤ x ≤ 4000000
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
• Ordinea lexicografică a caracterelor este: literele mici, iar apoi cele mari (în ordinea din alfabet), cifrele (în ordine crescătoare), iar apoi caracterele !, @, #, $, %, în această ordine.

Exemplul 1:

passwdIN.txt

1
1 1 1 1
66

passwdOUT.txt

aA@5

Explicație

p = 1

Atenție! Pentru acest test se rezolvă doar cerința a).

Exemplul 2:

passwdIN.txt

2
1 1 1 1
66

passwdOUT.txt

145187

Explicație

p = 1

Atenție! Pentru acest test se rezolvă doar cerința b).

Se observă că valoarea lui x nu este necesară în acest caz

Exemplul 3:

passwdIN.txt

2
1 1 1 2501
66

passwdOUT.txt

Datele nu corespund restrictiilor impuse

.

Rezolvare

<syntaxhighlight lang="python3" line="1"> MOD = 666013 nmax = 2501

def put(a, b):

   rez = 1
   while b:
       if b & 1:
           rez = (rez * a) % MOD
       a = (a * a) % MOD
       b >>= 1
   return rez

def preprocesare():

   fact[0] = 1
   inv[0] = 1
   fact[1] = 1
   inv[1] = 1
   for i in range(2, nmax * 4):
       fact[i] = (fact[i - 1] * i) % MOD
       inv[i] = put(fact[i], MOD - 2)

def comb(n, k):

   if n == k or k == 0:
       return 1
   rez = ((fact[n] * inv[n - k]) % MOD * inv[k]) % MOD
   return rez

def baga(pos, a, b, c, d):

   global gata, cntPasswd
   if pos == n + 1:
       cntPasswd += 1
       if cntPasswd == X:
           gata = True
           g.write("".join(Sol[1:n + 1]) + "\n")
           return
   else:
       if a:
           for i in range(97, 123):
               Sol[pos] = chr(i)
               baga(pos + 1, a - 1, b, c, d)
               if gata:
                   return
       if b:
           for i in range(65, 91):
               Sol[pos] = chr(i)
               baga(pos + 1, a, b - 1, c, d)
               if gata:
                   return
       if c:
           for i in range(48, 58):
               Sol[pos] = chr(i)
               baga(pos + 1, a, b, c - 1, d)
               if gata:
                   return
       if d:
           for i in v:
               Sol[pos] = i
               baga(pos + 1, a, b, c, d - 1)
               if gata:
                   return

def primaCerinta():

   v.extend(['!', '@', '#', '$', '%'])
   baga(1, a, b, c, d)

def a2Cerinta():

   preprocesare()
   rez = (comb(n, a) * put(26, a)) % MOD
   rez = (rez * comb(n - a, b)) % MOD
   rez = (rez * put(26, b)) % MOD
   rez = (rez * comb(n - a - b, c)) % MOD
   rez = (rez * put(10, c)) % MOD
   rez = (rez * comb(n - a - b - c, d)) % MOD
   rez = (rez * put(5, d)) % MOD
   g.write(f"{rez}\n")

def verifica_restrictii(a, b, c, d, X):

   if not (1 <= a <= 2500 and 1 <= b <= 2500 and 1 <= c <= 2500 and 1 <= d <= 2500 and 1 <= X <= 4000000):
       with open("passwdOUT.txt", "w") as g:
           g.write("Datele nu corespund restrictiilor impuse\n")
       return False
   return True

def rezolva():

   global n
   n = a + b + c + d
   if tip == 1:
       primaCerinta()
   else:
       a2Cerinta()

def main():

   global tip, a, b, c, d, X, v, cntPasswd, Sol, gata, fact, inv, n, g
   with open("passwdIN.txt", "r") as f:
       tip = int(f.readline().strip())
       a, b, c, d = map(int, f.readline().strip().split())
       X = int(f.readline().strip())

   if not verifica_restrictii(a, b, c, d, X):
       return

   v = []
   cntPasswd = 0
   Sol = [""] * (nmax * 4)
   gata = False
   fact = [0] * (nmax * 4)
   inv = [0] * (nmax * 4)

   with open("passwdOUT.txt", "w") as g:
       rezolva()

if __name__ == "__main__":

   main()

</syntaxhighlight>