0604 - Maria: Diferență între versiuni
(Pagină nouă: == Cerința == Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în n*m sectoare pătratice cu dimensiunea 1, dispuse pe n linii și m coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni p, q, cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze...) |
Fără descriere a modificării |
||
Linia 1: | Linia 1: | ||
== Cerința == | == Cerința == | ||
Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în n*m sectoare pătratice cu dimensiunea 1, dispuse pe n linii și m coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni p, q, cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze într-o zonă diferită de cele în care a dansat deja. Determinați numărul de zile în care Maria poate dansa așa cum își dorește. | Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în '''n*m''' sectoare pătratice cu dimensiunea '''1''', dispuse pe '''n''' linii și '''m''' coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni '''p''', '''q''', cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze într-o zonă diferită de cele în care a dansat deja. Determinați numărul de zile în care Maria poate dansa așa cum își dorește. | ||
== Date de intrare == | == Date de intrare == | ||
Fișierul de intrare mariain.txt conține pe prima linie numerele n m p q. A doua linie conține numărul k de sectoare din sală în care se află obstacole. Fiecare dintre următoarele k linii conține două numere i j, reprezentând linia și coloana unui sector ce conține un obstacol. | Fișierul de intrare '''mariain.txt''' conține pe prima linie numerele '''n m p q'''. A doua linie conține numărul '''k''' de sectoare din sală în care se află obstacole. Fiecare dintre următoarele '''k''' linii conține două numere '''i j''', reprezentând linia și coloana unui sector ce conține un obstacol. | ||
== Date de ieșire == | == Date de ieșire == | ||
Fișierul de ieșire mariaout.txt va conține pe prima linie numărul Z de zile în care Maria poate dansa în zone diferite. | Fișierul de ieșire '''mariaout.txt''' va conține pe prima linie numărul '''Z''' de zile în care Maria poate dansa în zone diferite. | ||
== Restricții și precizări == | == Restricții și precizări == | ||
*1 ⩽ n, m, p, q ⩽ 1000 | *'''1 ⩽ n, m, p, q ⩽ 1000''' | ||
*0 ⩽ k ⩽ 1000 | *'''0 ⩽ k ⩽ 1000''' | ||
*1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m | *'''1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m''' | ||
*două zone de dans sunt distincte dacă diferă prin cel puțin un sector | *două zone de dans sunt distincte dacă diferă prin cel puțin un sector | ||
*zona de dans poate fi orientată astfel încât să ocupe p linii și q coloane sau q linii și p coloane | *zona de dans poate fi orientată astfel încât să ocupe '''p''' linii și '''q''' coloane sau '''q''' linii și '''p''' coloane | ||
== Exemplu 1 == | == Exemplu 1 == | ||
;mariain.txt | ;'''mariain.txt''' | ||
:5 6 2 3 | :5 6 2 3 | ||
:3 | :3 | ||
Linia 18: | Linia 18: | ||
:3 5 | :3 5 | ||
:4 3 | :4 3 | ||
;mariaout.txt | ;'''mariaout.txt''' | ||
:5 | :5 | ||
<br> | <br> | ||
== Exemplu 2 == | == Exemplu 2 == | ||
;mariain.txt | ;'''mariain.txt''' | ||
:0 -1 -2 0 | :0 -1 -2 0 | ||
:-1 | :-1 | ||
:-3 -4 | :-3 -4 | ||
;mariaout.txt | ;'''mariaout.txt''' | ||
: Nu au fost respectate cerintele impuse | : Nu au fost respectate cerintele impuse | ||
<br> | <br> |
Versiunea curentă din 6 ianuarie 2024 13:03
Cerința
Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în n*m sectoare pătratice cu dimensiunea 1, dispuse pe n linii și m coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni p, q, cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze într-o zonă diferită de cele în care a dansat deja. Determinați numărul de zile în care Maria poate dansa așa cum își dorește.
Date de intrare
Fișierul de intrare mariain.txt conține pe prima linie numerele n m p q. A doua linie conține numărul k de sectoare din sală în care se află obstacole. Fiecare dintre următoarele k linii conține două numere i j, reprezentând linia și coloana unui sector ce conține un obstacol.
Date de ieșire
Fișierul de ieșire mariaout.txt va conține pe prima linie numărul Z de zile în care Maria poate dansa în zone diferite.
Restricții și precizări
- 1 ⩽ n, m, p, q ⩽ 1000
- 0 ⩽ k ⩽ 1000
- 1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m
- două zone de dans sunt distincte dacă diferă prin cel puțin un sector
- zona de dans poate fi orientată astfel încât să ocupe p linii și q coloane sau q linii și p coloane
Exemplu 1
- mariain.txt
- 5 6 2 3
- 3
- 2 2
- 3 5
- 4 3
- mariaout.txt
- 5
Exemplu 2
- mariain.txt
- 0 -1 -2 0
- -1
- -3 -4
- mariaout.txt
- Nu au fost respectate cerintele impuse
Rezolvare
#0604 - Maria
def is_valid_input(n, m, p, q, obstacles):
if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= p <= 1000 and 1 <= q <= 1000):
return False
if not (0 <= len(obstacles) <= 1000):
return False
for i, j in obstacles:
if not (1 <= i <= n and 1 <= j <= m):
return False
return True
def count_dance_days(n, m, p, q, obstacles):
dance_days = 0
for i in range(1, n - p + 2):
for j in range(1, m - q + 2):
valid_dance_zone = True
for k in range(p):
for l in range(q):
if (i + k, j + l) in obstacles:
valid_dance_zone = False
break
if not valid_dance_zone:
break
if valid_dance_zone:
dance_days += 1
for i in range(1, n - q + 2):
for j in range(1, m - p + 2):
valid_dance_zone = True
for k in range(q):
for l in range(p):
if (i + k, j + l) in obstacles:
valid_dance_zone = False
break
if not valid_dance_zone:
break
if valid_dance_zone:
dance_days += 1
return dance_days
def main():
try:
with open("mariain.txt", "r") as infile:
n, m, p, q = map(int, infile.readline().split())
k = int(infile.readline())
obstacles = [tuple(map(int, infile.readline().split())) for _ in range(k)]
except ValueError:
print("Nu au fost respectate cerintele impuse.")
return
if not is_valid_input(n, m, p, q, obstacles):
print("Nu au fost respectate cerintele impuse.")
return
result = count_dance_days(n, m, p, q, obstacles)
with open("mariaout.txt", "w") as outfile:
outfile.write(str(result))
if __name__ == "__main__":
main()