2616 - Paznici1

Cerință

Un parc de formă dreptunghiulară este împărțit în n * m sectoare, dispuse pe n linii și m coloane. Între oricare două sectoare învecinate, precum și pe exteriorul parcului sunt alei, ca în imaginea următoare (sectoarele sunt colorate cu verde, aleele cu gri):

Administrația parcului hotărăște angajarea unor paznici. Fiecare paznic va ocupa o poziție fixă pe o alee și va supraveghea sectoarele învecinate, ca mai jos. Astfel, un paznic poate supraveghea unul, două sau patru sectoare.

Scrieți un program care citește n și m și determină numărul minim de paznici care trebuie angajați pentru a supraveghea parcul în aceste condiții.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran numărul P, reprezentând valoarea cerută.

Restricții și precizări

1 ≤ n, m ≤ 1 000 000

Exemplul 1

Intrare

2 2

Ieșire

1

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1"> def validare(n, m):

   # Verifică dacă numărul de linii si de coloane apartine restrictiilor impuse
   if n < 1 or m < 1 or n > 1000000 or m > 1000000:
       return False
   return True

def numar_paznici(n, m):

   # Dacă numărul de rânduri este impar, îl facem par prin adăugarea unei unități.
   if n % 2 == 1:
       n += 1
   # Dacă numărul de coloane este impar, îl facem par prin adăugarea unei unități.
   if m % 2 == 1:
       m += 1
   # Numărul minim de paznici necesari este dat de suprafața totală a parcului,
   # împărțită la suprafața pe care o poate supraveghea un singur paznic (adică 2x2).
   # Pentru a face acest lucru, împărțim numărul de rânduri la 2 și numărul de coloane la 2,
   # apoi înmulțim rezultatul obținut.
   return (n // 2) * (m // 2)

if __name__ == "__main__":

   # Primește input-ul de la utilizator
   n = int(input("Introduceți numărul de rânduri: "))
   m = int(input("Introduceți numărul de coloane: "))

   # Verifică dacă input-ul este valid și afișează rezultatul
   if validare(n, m):
       print("Datele de intrare corespund restricțiilor impuse.")
       print(numar_paznici(n, m))
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>