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>