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

</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.