Editing 2906 - Potrivire

Sursa: [https://www.pbinfo.ro/probleme/2906/potrivire - Potrivire]
----
== Cerinţa ==
Gigel a găsit un șir de '''n''' cifre minunate. A adormit cu ele în brațe și a visat '''m''' numere naturale. Nedumerit, a cerut părerea vrăjitoarei Ghiocica. Acesta i-a spus:

* - Gigele, ești norocos. Suma numerelor distincte visate care sunt scrise cu cifre consecutive în șirul de cifre minunate este suma pe care o vei câștiga la Loto.

Nerăbdător, Gigel vă roagă să scrieți un program care să citească cele '''n''' cifre și cele '''m''' numere și să determine suma pe care o va câștiga la Loto.
== Date de intrare ==
Fișierul de intrare '''potrivire.in''' conține pe prima linie numărul '''n'''; a doua linie conține șirul de '''n''' cifre. A treia linie conține numărul '''m''', iar a patra linie conține cele '''m''' numere.
== Date de ieșire == 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
"Datele sunt corecte.", iar apoi in fișierul de ieșire '''potrivire.out''' va conține pe prima linie numărul '''S''', reprezentând suma pe care o va câștiga Gigel. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

== Restricţii şi precizări ==
* 1 ≤ '''n, m''' ≤ 100.000
* pentru 50% din teste, 1 ≤ '''n, m''' ≤ 1000
* cele '''m''' numere visate sunt numere naturale și au cel mult cinci cifre
== Exemple ==
===Exemplul 1===
; potrivire.in
: 10
: 4 5 6 2 6 0 7 1 9 7
: 6
: 456 662 2607 2607 97 975
; Ieșire
: Datele sunt corecte.
; potrivire.out
: 3160
===Exemplul 2===
; potrivire.in
: 6
: 1 0 3 1 4 5
: 8 
: 111 1231 4124 5741 4124 22 21 12
; Ieșire
: Datele sunt corecte.
; potrivire.out
: 0
===Exemplul 3===
; potrivire.in
: 10
: 4 5 6 2 6 0 7 1 9 7
: 2
: 12414124215 1251251512
; Ieșire
: Datele nu sunt comform restricțiilor impuse.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#2906 - Potrivire


def potrivire(n, cifre, m, numere_visate):
    f = open("potrivire.out", "w")
    frecventa = {}
    s = 0
    for i in range(n):
        num = 0
        for j in range(i, min(i + 4, n)):
            num = num * 10 + cifre[j]
            if num not in frecventa:
                frecventa[num] = 0
            frecventa[num] += 1
    for i in range(m):
        if numere_visate[i] in frecventa and frecventa[numere_visate[i]] != 0 and frecventa[numere_visate[i]] != -1:
            s += numere_visate[i]
            frecventa[numere_visate[i]] = -1
    f.write(str(s))
    f.close()

def conform_restrictiilor():
    with open("potrivire.in", "r") as f:
        n = int(f.readline())
        cifre = list(map(int, f.readline().split()))
        m = int(f.readline())
        numere_visate = list(map(int, f.readline().split()))
        if not (1 <= m <= 100000) and not (1 <= n <= 100000):
            print("Datele nu sunt conform restricțiilor impuse.")
            exit()
        for x in numere_visate:
            if x > 100000:
                print("Datele nu sunt conform restricțiilor impuse.")
                exit()
        for x in cifre:
            if x >= 10:
                print("Datele nu sunt conform restricțiilor impuse.")
                exit()
        print("Datele sunt corecte.")
        return n, cifre, m, numere_visate

if __name__ == '__main__':
    n, cifre, m, numere_visate = conform_restrictiilor()
    potrivire(n, cifre, m, numere_visate)
</syntaxhighlight>

==Explicaţie cod==

Funcția '''conform_restrictiilor()''' verifică dacă datele de intrare sunt conforme cu restricțiile impuse în problemă, respectiv: '''n''' și '''m''' trebuie să fie între 1 și 100.000, inclusiv, cifre și numere_visate trebuie să conțină numere între 0 și 100.000, inclusiv, iar cifrele din cifre trebuie să fie mai mici decât 10.

Funcția '''potrivire()''' primește ca argumente '''n''', '''cifre''', '''m''' și '''numere_visate''', determină toate numerele care pot fi formate prin combinarea unui subset de cifre consecutive din cifre, și calculează suma tuturor numerelor din numere_visate care se regăsesc printre numerele calculate. Aceasta se realizează prin parcurgerea tuturor subset-urilor de cifre consecutive și adăugarea numerelor rezultate într-un dicționar care memorează frecvența aparițiilor acestora. Apoi, pentru fiecare număr din numere_visate, se verifică dacă acesta se regăsește în dicționar și dacă apare cel puțin o dată și nu a fost deja adăugat la sumă.

La final, suma calculată este scrisă în fișierul '''potrivire.out'''.