Latest revision as of 13:07, 7 January 2024

Cerința[edit | edit source]

Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

Date de intrare[edit | edit source]

Programul citește de la tastatură numerele n m, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi m triplete i j p, reprezentând muchiile, date prin extremități și pondere.

Date de ieșire[edit | edit source]

Programul va afișa pe ecran numărul vf, reprezentând vârful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

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

1 ≤ n ≤ 100
ponderile muchiilor sunt numere naturale nenule mai mici decât 1000
graful dat nu conține noduri izolate

Exemplul 1:[edit | edit source]

Intrare

Ieșire

Explicație[edit | edit source]

Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt:

pentru vârful 1 media este 10
pentru vârful 2 media este 4.66667
pentru vârful 3 media este 5
pentru vârful 4 media este 3
pentru vârful 5 media este 6.33333

Astfel media minimă este 3, pentru vârful 4

Exemplul 2:[edit | edit source]

Intrare

consola

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> from typing import List, Tuple

def check_constraints(n, m, edges):

   if not (1 <= n <= 100):
       return False
   for edge in edges:
       i, j, p = edge
       if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
           return False
   return True

def main():

   nMAX = 100
   mat = [[] for _ in range(nMAX + 1)]  # mat[i][0] = (j, p) (edge between i and j with weight p)

   n, m = map(int, input().split())

   if not (1 <= n <= 100):
       print("Detele nu respecta restrictiile impuse")
       return

   edges = [tuple(map(int, input().split())) for _ in range(m)]

   if not check_constraints(n, m, edges):
       print("Detele nu respecta restrictiile impuse")
       return

   for i, j, p in edges:
       mat[i].append((j, p))
       mat[j].append((i, p))

   vfmin = 0
   medmin = float('inf')

   for i in range(1, n + 1):
       _sum = sum(weight for _, weight in mat[i])
       if _sum / len(mat[i]) < medmin:
           medmin = _sum / len(mat[i])
           vfmin = i

   print(vfmin)

if __name__ == "__main__":

   main()

</syntaxhighlight>

@@ Line 6: / Line 6: @@
 = Date de ieșire =
-Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.
+Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".
 = Restricții și precizări =
@@ Line 45: / Line 45: @@
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def verifica_restricții(n, m, muchii):
+from typing import List, Tuple
-    # Verificăm restricțiile
-     if not (1 <= n <= 100) or any(not (1 <= vf1 <= n and 1 <= vf2 <= n) for vf1, vf2, _ in muchii) or any(not (1 <= p < 1000) for _, _, p in muchii):
+def check_constraints(n, m, edges):
+     if not (1 <= n <= 100):
          return False
+    for edge in edges:
+        i, j, p = edge
+        if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
+            return False
      return True
-def gaseste_varf_minim_media_ponderilor(n, m, muchii):
+def main():
-     # Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf
+     nMAX = 100
-     ponderi_vf = {i: [] for i in range(1, n + 1)}
+     mat = [[] for _ in range(nMAX + 1)]  # mat[i][0] = (j, p) (edge between i and j with weight p)
+    n, m = map(int, input().split())
+    if not (1 <= n <= 100):
+        print("Detele nu respecta restrictiile impuse")
+        return
-     # Citim și memorăm ponderile muchiilor în dicționar
+     edges = [tuple(map(int, input().split())) for _ in range(m)]
-    for i in range(m):
-        vf1, vf2, pondera = muchii[i]
-        ponderi_vf[vf1].append(pondera)
-        ponderi_vf[vf2].append(pondera)
-     # Calculăm media aritmetică a ponderilor pentru fiecare vârf
+     if not check_constraints(n, m, edges):
-    medii_ponderi = {vf: sum(ponderi) / len(ponderi) for vf, ponderi in ponderi_vf.items()}
+        print("Detele nu respecta restrictiile impuse")
+        return
-     # Găsim vârful cu media minimă
+     for i, j, p in edges:
-    vf_min_media = min(medii_ponderi, key=medii_ponderi.get)
+        mat[i].append((j, p))
+        mat[j].append((i, p))
-     return vf_min_media
+     vfmin = 0
+    medmin = float('inf')
-# Citirea numărului de vârfuri
+    for i in range(1, n + 1):
-n = int(input("Introduceți numărul de vârfuri "))
+        _sum = sum(weight for _, weight in mat[i])
-if not (1 <= n <= 100):
+        if _sum / len(mat[i]) < medmin:
-    print("Datele nu corespund restrictiilor impuse")
+            medmin = _sum / len(mat[i])
-else:
+            vfmin = i
-    # Citirea numărului de muchii
-    m = int(input("Introduceți numărul de muchii: "))
-    # Citirea muchiilor și ponderilor
+     print(vfmin)
-     print("Introduceți extremitățile și ponderea fiecărei muchii:")
-    muchii = [tuple(map(int, input().split())) for _ in range(m)]
-    # Apelarea funcției și afișarea rezultatului
+if __name__ == "__main__":
-    rezultat = gaseste_varf_minim_media_ponderilor(n, m, muchii)
+     main()
-     if rezultat is not None:
-        print(rezultat)
 </syntaxhighlight>