3738 - New York

Cerința

Doru s-a mutat în New York și își caută o nouă locuință specială în perimetrul străzilor numerotate cu numerele distincte de la 1 la n. Fiind pasionat de matematică, el vrea să se mute pe strada în care cel mai mare divizor comun (cmmdc) al înălțimilor clădirilor este maxim.

În plus, alegerea clădirii nu este una ușoară, el dorind să se mute doar într-o clădire perfectă. Numim o clădire perfectă o clădire care are cea mai mare înălțime număr prim de pe strada pe care se află.

Fiind ocupat cu împachetatul, Doru vă roagă pe voi să găsiți clădirea perfectă.

Date de intrare

Fișierul de intrare nykin.txt conține pe prima linie numărul de străzi n pe care Doru își caută noua locuință. Pe fiecare dintre următoarele n linii (câte una pentru fiecare stradă din cele n, în ordinea crescătoare a numerelor străzilor) se află numărul m, reprezentând numărul de clădiri de pe strada curentă, urmat de m numere ce reprezintă înălțimile clădirilor de pe strada curentă (în ordinea poziționării lor pe stradă, de la stânga la dreapta). Pe fiecare linie numerele sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire nykout.txt va conține două linii.

Prima linie va conține două numere naturale separate printr-un spațiu, reprezentând numărul străzii cerute și poziția pe stradă a clădirii în care se va muta Doru.

A doua linie va conține un număr natural reprezentând înălțimea clădirii alese.

Dacă pe strada cu cmmdc-ul maxim nu se găsește nicio clădire cu înălțimea un număr prim, atunci prima linie a fișierului va conține mesajul Nu am gasit casa!

Restricții și precizări

• 1 ⩽ n ⩽ 1000
• 1 ⩽ m ⩽ 1000
• Numerele de pe a doua linie a fișierului de intrare sunt mai mici decât 1 000 000 000
• Înălțimile clădirilor sunt numere naturale nenule mai mici ca 2 000 000 000.
• Pe fiecare stradă există cel puțin o clădire.
• Dacă pe strada cu cmmdc-ul maxim sunt mai multe clădiri perfecte, se va afișa cea mai din dreapta.
• Dacă sunt mai multe străzi cu aceeași clădire perfectă, se va afișa cea care are numărul străzii cel mai mare.

Exemplu 1

nykin.txt

5

2 1 2

3 18 6 48

2 5 7

4 3 6 9 12

4 34 17 68 17

nykout.txt

5 4

17

Explicatie

Valoarea maximă a celui mai mare divizor comun al înălțimilor clădirilor de pe o stradă dintre cele cinci este 17 (cmmdc(1,2)=1, cmmdc(18, 6, 48)=6, cmmdc(5, 7)=1, cmmdc(3, 6, 9, 12)=3, cmmdc(34, 17, 68, 17)=17). Astfel Doru va alege clădirea a 4-a de pe strada cu numărul 5.

Exemplu 2

nykin.txt

0

-1 -3

nykut.txt

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 3738 - New York

def check_restrictions(n, m_values):

   if not (1 <= n <= 1000):
       return False

   for m, *heights in m_values:
       if not (1 <= m <= 1000):
           return False

       if not all(0 < height < 2000000000 for height in heights):
           return False

   return True

def find_perfect_building(n, m_values):

   if not check_restrictions(n, m_values):
       print("Date de intrare invalide!")
       return None

   max_gcd = 0
   selected_street = 0
   selected_position = 0

   for street, *heights in m_values:
       current_gcd = heights[0]
       for height in heights[1:]:
           current_gcd = gcd(current_gcd, height)

       if current_gcd > max_gcd:
           max_gcd = current_gcd
           selected_street = street
           selected_position = len(heights)

       elif current_gcd == max_gcd and street >= selected_street:
           selected_street = street
           selected_position = len(heights)

   if max_gcd == 1:
       print("Nu am gasit casa!")
       return None

   return selected_street, selected_position, max_gcd

def gcd(a, b):

   while b:
       a, b = b, a % b
   return a

1. Citire date de intrare

try:

   with open("nykin.txt", "r") as file:
       n = int(file.readline())
       m_values = [list(map(int, line.split())) for line in file.readlines()]

except FileNotFoundError:

   print("Fisierul de intrare nu exista!")
   exit()

1. Calcul și scriere rezultat în fișierul de ieșire

result = find_perfect_building(n, m_values) if result is not None:

   with open("nykout.txt", "w") as file:
       file.write(f"{result[0]} {result[1]}\n{result[2]}\n")

</syntaxhighlight>