1751 - Icsuri: Difference between revisions

Latest revision as of 21:27, 2 June 2024

Cerința[edit | edit source]

În clasa a IX-a A sunt M elevi, numerotați de la 1 la M și fiecare are un număr preferat P. Plictisiți de ora de informatică, au inventat următorul joc:

pe o foaie de matematică desenează o tablă de joc de dimensiune N, formată din N linii și N coloane, numerotate de la 1 la N; fiecare linie și fiecare coloană are câte N pătrățele fiecare elev alege un pătrățel și desenează un X centrat în pătrățelul ales, fiecare din cele 4 laturi având cel mult P pătrățele desenate, fără a ieși de pe tabla de joc (să nu mâzgălească banca!!). icsurile desenate de elevi se pot suprapune. Cunoscând dimensiunea N a tablei de joc, numărul M de elevi, coordonatele alese de fiecare elev și numărul preferat al fiecărui elev, determinați câte pătrățele de pe tablă rămân nedesenate.

Date de intrare[edit | edit source]

Programul citește de la tastatură numărul N M, iar apoi M triplete i j p, reprezentând coordonatele pătrățelului ales și numărul preferat de fiecare elev.

Date de ieșire[edit | edit source]

Programul va afișa pe ecran numărul de pătrățele nedesenate.

Restricții și precizări[edit | edit source]

1 ≤ N ≤ 1000
1 ≤ M ≤ 100000
1 ≤ i,j ≤ N
0 ≤ p ≤ N/2

Exemplu 1[edit | edit source]

Intrare

10 5
1 2 1
6 6 3
7 3 2
2 5 2
9 8 3

Iesire

62

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line> def citire_date():

   import sys
   input = sys.stdin.read
   data = input().split()
   N = int(data[0])
   M = int(data[1])
   elevi = []
   index = 2
   for _ in range(M):
       i = int(data[index])
       j = int(data[index+1])
       p = int(data[index+2])
       elevi.append((i, j, p))
       index += 3
   return N, M, elevi

def deseneaza_patratele(N, elevi):

   tabla = [[0] * N for _ in range(N)]
   for i, j, p in elevi:
       for x in range(max(0, i - p), min(N, i + p + 1)):
           for y in range(max(0, j - p), min(N, j + p + 1)):
               if abs(x - i) + abs(y - j) <= p:
                   tabla[x][y] = 1
   numar_patratele_nedesenate = sum(row.count(0) for row in tabla)
   return numar_patratele_nedesenate

def main():

   N, M, elevi = citire_date()

   # Verificarea restrictiilor
   assert 1 <= N <= 1000, "N trebuie sa fie intre 1 si 1000"
   assert 1 <= M <= 100000, "M trebuie sa fie intre 1 si 100000"
   for i, j, p in elevi:
       assert 1 <= i <= N, "i trebuie sa fie intre 1 si N"
       assert 1 <= j <= N, "j trebuie sa fie intre 1 si N"
       assert 0 <= p <= N // 2, "p trebuie sa fie intre 0 si N//2"

   rezultat = deseneaza_patratele(N, elevi)
   print(rezultat)

if __name__ == "__main__":

   main()

</syntaxhighlight>

@@ Line 1: / Line 1: @@
 == Cerința ==
-Într-un regat îndepărtat, există un joc popular printre copii numit "X-uri Magice". În acest joc, copiii desenează două matrici pătratice și încearcă să găsească toate valorile comune dintre cele două matrici. Fiecare matrice este formată din numere întregi, iar scopul este de a găsi toate numerele comune (valori identice) din cele două matrici și să le ordoneze într-o listă crescătoare.
+În clasa a IX-a A sunt M elevi, numerotați de la 1 la M și fiecare are un număr preferat P. Plictisiți de ora de informatică, au inventat următorul joc:
+pe o foaie de matematică desenează o tablă de joc de dimensiune N, formată din N linii și N coloane, numerotate de la 1 la N; fiecare linie și fiecare coloană are câte N pătrățele
+fiecare elev alege un pătrățel și desenează un X centrat în pătrățelul ales, fiecare din cele 4 laturi având cel mult P pătrățele desenate, fără a ieși de pe tabla de joc (să nu mâzgălească banca!!).
+icsurile desenate de elevi se pot suprapune.
+Cunoscând dimensiunea N a tablei de joc, numărul M de elevi, coordonatele alese de fiecare elev și numărul preferat al fiecărui elev, determinați câte pătrățele de pe tablă rămân nedesenate.
 == Date de intrare ==
-Programul citește de la tastatură două matrici pătratice de numere întregi.
+Programul citește de la tastatură numărul N M, iar apoi M triplete i j p, reprezentând coordonatele pătrățelului ales și numărul preferat de fiecare elev.
 == Date de ieșire ==
-Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."
+Programul va afișa pe ecran numărul de pătrățele nedesenate.
-În următorul rând se va afișa pe ecran lista cu valorile comune ale celor două matrici. Dacă nu există valori comune, se va afișa o listă goală.
-În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."
 == Restricții și precizări ==
-* 1 &les; '''n (dimensiune matrice)''' &les; 1000
+*1 ≤ N ≤ 1000
+*1 ≤ M ≤ 100000
+*1 ≤ i,j ≤ N
+*0 ≤ p ≤ N/2
 == Exemplu 1 ==
 ;Intrare
-<br>
+5<br>
-2 3 <br>
+2 1<br>
-5 6 <br>
+6 3<br>
-8 9<br><br>
+3 2<br>
-<br>
+5 2<br>
-2 3<br>
+8 3
-0 6<br>
-8 1<br>
 ;Iesire
-Datele de intrare corespund restricțiilor impuse.
-[1, 2, 3, 4, 6, 7, 8]
 == Rezolvare ==
 <syntaxhighlight lang="python" line>
-def citeste_matrice_patratica():
+def citire_date():
-     try:
+     import sys
-        n = int(input("Introduceți dimensiunea matricii pătratice (n): "))
+    input = sys.stdin.read
-         matrice = []
+    data = input().split()
-         for _ in range(n):
+    N = int(data[0])
-            rand = list(map(int, input().split()))
+    M = int(data[1])
-            if len(rand) != n:
+    elevi = []
-                return None
+    index = 2
-            matrice.append(rand)
+    for _ in range(M):
-        return matrice
+        i = int(data[index])
-     except ValueError:
+        j = int(data[index+1])
-        return None
+         p = int(data[index+2])
+        elevi.append((i, j, p))
+         index += 3
+    return N, M, elevi
+def deseneaza_patratele(N, elevi):
+    tabla = [[0] * N for _ in range(N)]
+    for i, j, p in elevi:
+        for x in range(max(0, i - p), min(N, i + p + 1)):
+            for y in range(max(0, j - p), min(N, j + p + 1)):
+                if abs(x - i) + abs(y - j) <= p:
+                    tabla[x][y] = 1
+    numar_patratele_nedesenate = sum(row.count(0) for row in tabla)
+     return numar_patratele_nedesenate
-def valideaza_date(matrice1, matrice2):
+def main():
-     if matrice1 and matrice2:
+     N, M, elevi = citire_date()
-        if len(matrice1) == len(matrice2) and len(matrice1) <= 1000:
-            if all(len(rand) == len(matrice1) for rand in matrice1) and all(len(rand) == len(matrice2) for rand in matrice2):
-                if all(-10**9 <= elem <= 10**9 for rand in matrice1 for elem in rand) and all(-10**9 <= elem <= 10**9 for rand in matrice2 for elem in rand):
-                    return True
-    return False
-def intersectie_matrici(matrice1, matrice2):
+    # Verificarea restrictiilor
-     set1 = {elem for rand in matrice1 for elem in rand}
+    assert 1 <= N <= 1000, "N trebuie sa fie intre 1 si 1000"
-     set2 = {elem for rand in matrice2 for elem in rand}
+     assert 1 <= M <= 100000, "M trebuie sa fie intre 1 si 100000"
-    intersectie = list(set1 & set2)
+     for i, j, p in elevi:
-    intersectie.sort()
+        assert 1 <= i <= N, "i trebuie sa fie intre 1 si N"
-    return intersectie
+        assert 1 <= j <= N, "j trebuie sa fie intre 1 si N"
+        assert 0 <= p <= N // 2, "p trebuie sa fie intre 0 si N//2"
-def main():
+     rezultat = deseneaza_patratele(N, elevi)
-     print("Introduceți prima matrice pătratică:")
+    print(rezultat)
-    matrice1 = citeste_matrice_patratica()
-    print("Introduceți a doua matrice pătratică:")
-    matrice2 = citeste_matrice_patratica()
-    if matrice1 is None or matrice2 is None:
-        print("Datele de intrare nu corespund restricțiilor impuse.")
-        return
-    if valideaza_date(matrice1, matrice2):
-        print("Datele de intrare corespund restricțiilor impuse.")
-        rezultat = intersectie_matrici(matrice1, matrice2)
-        print(rezultat)
-    else:
-        print("Datele de intrare nu corespund restricțiilor impuse.")
 if __name__ == "__main__":
      main()
 </syntaxhighlight>