3934 - parale

Sursa: - parale

---

Cerinţa

Dorel a primit de ziua lui o tablă cu n linii şi n coloane, numerotate de la 1 la n, şi m numere naturale cuprinse între 2 şi 2•n. Pentru fiecare număr natural x dintre cele m, el colorează pătrăţelele tablei care au suma indicilor multipli de x. Aflaţi câte pătrăţele rămân necolorate.

Date de intrare

Fișierul de intrare parale.in conține pe prima linie numerele naturale n şi m, iar pe următoarea linie cele m numere naturale, separate prin câte un spaţiu.

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 parale.out va conține pe prima linie numărul pătrăţelelor necolorate. Î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

Exemple

Exemplul 1

parale.in

8 3

2 3 4

Ieșire

Datele sunt corecte.

parale.out

20

Exemplul 2

parale.in

8 4

4 6 14

Ieșire

Datele sunt corecte.

parale.out

40

Exemplul 3

parale.in

2 2

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3934 - parale

def parale(vector,n):

   f = open("parale.out", "w")
   numar_patrate_colorate = 0
   for i in range(1, n + 1):
       for j in range(1, n+1):
           for x in vector:
               if (i + j) % x ==0:
                   numar_patrate_colorate += 1
                   break
   numar_patrate_necolorate= (n*n) - numar_patrate_colorate
   f.write(str(numar_patrate_necolorate))
   
   

def conform_restrictiilor():

   with open("parale.in", "r") as f:
       n , m = map(int, f.readline().split())
       vector = list(map(int, f.readline().split()))
       if not (2 <= n <= 100000 and 2 <= m <= 100000):
           print("Datele nu sunt conform restricțiilor impuse.")
           exit()
       for x in vector:
           if x > 2*n:
               print("Datele nu sunt conform restricțiilor impuse.")
               exit()
       print("Datele sunt corecte.")
       return vector, n
       

if __name__ == '__main__':

   vector , n = conform_restrictiilor()
   parale(vector , n)

</syntaxhighlight>

Explicaţie cod

Funcția conform_restrictiilor() citește datele din fișierul parale.in, care trebuie să conțină două numere întregi separate prin spațiu: n și m, și un vector de lungime m de numere întregi separate prin spațiu. Prima valoare reprezintă dimensiunea unei matrici pătratice, iar restul valorilor reprezintă numere întregi ce vor fi folosite pentru a colora unele pătrate din această matrice. Această funcție verifică dacă valorile citite respectă restricțiile impuse (adica dimensiunea matricii și numărul de culori trebuie să fie între 2 și 100000), și returnează vectorul și lungimea matricii.

Funcția parale(vector,n) primește vectorul de culori și dimensiunea matricii. Această funcție iterează prin fiecare pătrat din matrice și verifică dacă suma coordonatelor pătratului respectiv este divizibilă cu cel puțin unul dintre elementele vectorului. Dacă pătratul este divizibil cu cel puțin o culoare, atunci acesta va fi considerat colorat și numărul de pătrate colorate va fi incrementat. La final, această funcție scrie în fișierul parale.out numărul de pătrate necolorate (lungimea matricii la pătrat minus numărul de pătrate colorate).

În secțiunea if __name__ == '__main__':, se apelează mai întâi funcția conform_restrictiilor() pentru a citi datele din fișier și a verifica dacă sunt conform restricțiilor. Apoi, se apelează funcția parale(vector,n) pentru a calcula numărul de pătrate necolorate și a scrie rezultatul în fișierul parale.out.