2781 - Wildfire

Sursă: [1]

Enunț

Se consideră o pădure ce conține n•m copaci aranjați pe n linii și m coloane în care s-a produs un incendiu. Pădurarii cunosc coordonatele x și y ale copacului de la care a izbucnit focul și modalitatea prin care acesta se extinde. Astfel, dacă un copac se aprinde într-o anumită zi, în ziua următoare se vor aprind copacii vecini cu acesta pe linie sau coloană care nu sunt încă afectați de incendiu.

Cerință

Știind x și y, coordonatele inițiale ale focului și n și m, dimensiunile pădurii, ajutați pădurarii să determine numărul minim de zile după care întreaga pădure va fi afectată.

Date de intrare

Programul citește de la tastatură numerele x y n m, cu semnificația de mai sus.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.".Programul va afișa pe ecran numărul Z, reprezentând numărul de zile după care va fi afectată întreaga pădure. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricții și precizări

• 1 ≤ x ≤ n ≤ 1.000.000.000
• 1 ≤ y ≤ m ≤ 1.000.000.000

Exemple

Exemplu 1

În funcție de numărul de zile, fiecare zonă va fi distrusă în numărul de zile corespunzător figurii de mai jos:

Intrare

2 2 4 5

Ieșire

6

Exemplu 2

Intrare

2 2 0 6

Ieșire

Datele nu sunt comform restricțiilor impuse

Exemplu 3

Intrare

2 -2 0 5

Ieșire

Datele nu sunt comform restricțiilor impuse

Explicație

În funcție de numărul de zile, fiecare zonă va fi distrusă în numărul de zile corespunzător figurii de mai jos:

Exemplu 2

Intrare

3 3 9 9

Ieșire

13

Explicație

În funcție de numărul de zile, fiecare zonă va fi distrusă în numărul de zile corespunzător figurii de mai jos:

5 4 3 4 5 6 7 8 9

4 3 2 3 4 5 6 7 8

3 2 1 2 3 4 5 6 7

4 3 2 3 4 5 6 7 8

5 4 3 4 5 6 7 8 9

6 5 4 5 6 7 8 9 10

7 6 5 6 7 8 9 10 11

8 7 6 7 8 9 10 11 12

9 8 7 8 9 10 11 12 13

Rezolvare

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

   valori = []
   for i in range(4):
       while True:
           try:
               valoare = int(input("Introduceti o valoare: "))
               if valoare >= 1 and valoare <= 1000000000:
                   print("Datele sunt corecte.")
                   valori.append(valoare)
                   break
               else:
                   print("Datele nu sunt conform restricțiilor impuse.")
           except ValueError:
               print("Trebuie introduse doar valori naturale cu mai putin de 10 cifre.")
   return valori

def numar_zile(valori):

   x, y, n, m = valori
   lc1 = x + y - 2
   lc2 = x - 1 + m - y
   lc3 = y - 1 + n - x
   lc4 = m - y + n - x
   return max(lc1, lc2, lc3, lc4) + 1

if __name__ == '__main__':

   valori = citeste_valori()
   Z = numar_zile(valori)
   print("Numărul de zile după care va fi afectată întreaga pădure este:", Z)

</syntaxhighlight>

Explicații

citeste_valori(): Această funcție citește de la tastatură patru valori întregi și le validează astfel încât să se încadreze în anumite restricții. Dacă valorile nu se încadrează în aceste restricții, utilizatorul este notificat și trebuie să introducă din nou valorile până când acestea sunt corecte. Funcția returnează lista valorilor corecte.

numar_zile(): Această funcție primește o listă de patru valori întregi și calculează numărul de zile după care va fi afectată întreaga pădure. Acest calcul este realizat folosind patru formule matematice, care iau în considerare poziția arborelui inițial (x, y) și a celui final (n, m). Funcția returnează numărul de zile calculat.

La final, programul apelează cele două funcții și afișează numărul de zile obținut.