Ramona Dragoș at 13:03, 6 January 2024

2024-01-06T13:03:13Z

← Older revision		Revision as of 13:03, 6 January 2024
Line 1:		Line 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 &les; n, m, p, q &les; 1000		*'''1 &les; n, m, p, q &les; 1000'''
	*0 &les; k &les; 1000		*'''0 &les; k &les; 1000'''
	*1 &les; i &les; n, 1 &les; j &les; m		*'''1 &les; i &les; n, 1 &les; j &les; 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
Line 18:		Line 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>

Ramona Dragoș: 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...

2023-12-15T17:40:26Z

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...

New page

== 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 &les; n, m, p, q &les; 1000
*0 &les; k &les; 1000
*1 &les; i &les; n, 1 &les; j &les; 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
<br>
== Exemplu 2 ==
;mariain.txt
:0 -1 -2 0
:-1
:-3 -4
;mariaout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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()

</syntaxhighlight>

0604 - Maria - Revision history

Ramona Dragoș at 13:03, 6 January 2024