2619 – Five

Sursa: [1]

---

Enunt

Se consideră un șir de numere naturale a[1], a[2], …, a[n].

Cerinta

Să se determine numărul tripletelor (a[i], a[j], a[p]) cu i < j < p, iar a[i] + a[j] + a[p] este divizibil cu 5.

Date de intrare

Programul citește de la tastatură numerele n, w, X, Y, Z. Șirul de n numere se generează după relațiile: a[1] = w, a[i] = (X * a[i-1] + Y) % Z;

Date de iesire

Programul va afișa pe ecran numărul tripletelor cu suma divizibilă cu 5.

Restrictii si precizari

• 1 ≤ n ≤ 100.000
• 1 ≤ w, X, Y, Z ≤ 1.000.000.000

Exemplu

Intrare

10 1 7 223 17

Iesire

24

Rezolvare

<syntaxhighlight lang="python" line>

def numar_tripleturi_divizibile_cu_5(n, w, X, Y, Z):

   # Generăm șirul a
   a = [w]
   for i in range(1, n):
       a.append((X * a[i-1] + Y) % Z)

   # Numărul de tripleturi divizibile cu 5
   count = 0

   # Parcurgem fiecare triplet de indici (i, j, p)
   for i in range(n):
       for j in range(i+1, n):
           for p in range(j+1, n):
               if (a[i] + a[j] + a[p]) % 5 == 0:
                   count += 1

   return count

if __name__ == '__main__':

   # Citim valorile de la tastatură
   try:
       n, w, X, Y, Z = map(int, input("Introduceti valorile pentru n, w, X, Y, Z: ").split())

       # Validăm restricțiile de intrare
       if n < 1 or n > 100000:
           raise ValueError("n trebuie să fie între 1 și 100000")
       if w < 1 or w > 1000000000:
           raise ValueError("w trebuie să fie între 1 și 1000000000")
       if X < 1 or X > 1000000000:
           raise ValueError("X trebuie să fie între 1 și 1000000000")
       if Y < 1 or Y > 1000000000:
           raise ValueError("Y trebuie să fie între 1 și 1000000000")
       if Z < 1 or Z > 1000000000:
           raise ValueError("Z trebuie să fie între 1 și 1000000000")

       # Apelăm funcția pentru a calcula numărul de tripleturi divizibile cu 5
       rezultat = numar_tripleturi_divizibile_cu_5(n, w, X, Y, Z)

       # Afișăm rezultatul
       print("Numărul de tripleturi cu suma divizibilă cu 5:", rezultat)

   except ValueError as e:
       print("Eroare:", e)
   except:
       print("Eroare neașteptată.")

</syntaxhighlight>