Editing 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 <code>a</code> litere mici ale alfabetului englez și <code>b</code> litere mari ale alfabetului englez, <code>c</code> cifre si <code>d</code> caractere din mulțimea <code>{!, @, #, $, %}</code>. Totodată, el vrea să găsească parola cu numărul <code>x</code> în ordine lexicografică, formată din caracterele descrise mai sus.

= Cerința =
Cunoscând <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code> si <code>x</code> se cere:

a) A <code>x</code>-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 <code>666013</code>.

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

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

= Date de ieșire =
Dacă valoarea lui <code>p</code> este <code>1</code>, se va rezolva numai punctul a) din cerință.

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

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

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

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

= Restricții și precizări =

* <code>1 ≤ a, b, c, d ≤ 2500</code>
* <code>1 ≤ x ≤ 4000000</code>
* 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 <code>!, @, #, $, %</code>, în această ordine.

= Exemplul 1: =
<code>passwdIN.txt</code>
 1
 1 1 1 1
 66
<code>passwdOUT.txt</code>
 aA@5

= Explicație =
<code>p = 1</code>

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

= Exemplul 2: =
<code>passwdIN.txt</code>
 2
 1 1 1 1
 66
<code>passwdOUT.txt</code>
 145187

= Explicație =
<code>p = 1</code>

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: =
<code>passwdIN.txt</code>
 2
 1 1 1 2501
 66
<code>passwdOUT.txt</code>
 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>