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
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." și programul va afișa pe ecran numărul P, reprezentând valoarea cerută. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."
Restricții și precizări
1 ≤ n, m ≤ 1 000 000
Exemplul 1
- Intrare
- 2
- 2
- Ieșire
- Datele de intrare corespund restricțiilor impuse.
- 1
Rezolvare
Rezolvare ver. 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.")