2636 - Noduri Izolate

From Bitnami MediaWiki
Revision as of 14:29, 16 December 2023 by Corjuc Eunice (talk | contribs) (Pagină nouă: = Cerința = Se dau două numere <code>n</code> și <code>m</code>. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu <code>n</code> noduri și <code>m</code> muchii în care nu există o muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie. = Date de intrare = Programul citește de la tastatură numerele <code>n m</code>. = Date de ieșire = Programul va afișa pe ecran numerel...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Cerința

Se dau două numere n și m. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există o muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

Date de intrare

Programul citește de la tastatură numerele n m.

Date de ieșire

Programul va afișa pe ecran numerele a și b, reprezentând numărul minim, respectiv numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există o muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

Restricții și precizări

  • 1 ≤ n ≤ 100.000
  • 0<=m<=n*(n-1)/2

Exemplul 1

Input:

4 2

Output:

0 1

Exemplul 2

Input:

99999999 2

Output:

Restrictiile nu sunt indeplinite.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def check_restrictions(n, m):

   return 1 <= n <= 100000 and 0 <= m <= n * (n - 1) // 2

def calculate_isolated_nodes(n, m):

   # Verifică restricțiile
   if not check_restrictions(n, m):
       print("Restrictiile nu sunt indeplinite.")
       return None
   # Numărul minim de noduri izolate
   min_isolated_nodes = 0
   # Numărul maxim de noduri izolate
   max_isolated_nodes = max(0, min(n - m, 1))
   return min_isolated_nodes, max_isolated_nodes

if __name__ == "__main__":

   n = int(input("Introduceti numarul de noduri (n): "))
   m = int(input("Introduceti numarul de muchii (m): "))
   result = calculate_isolated_nodes(n, m)
   if result is not None:
       min_isolated, max_isolated = result
       print(f"Numarul minim de noduri izolate: {min_isolated}")
       print(f"Numarul maxim de noduri izolate: {max_isolated}")

</syntaxhighlight>