2906 - Potrivire

Sursa: - 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.

Rezolvare

#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)

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.