4044 - camere - Revision history

Cata at 05:45, 3 May 2023

2023-05-03T05:45:26Z

← Older revision		Revision as of 05:45, 3 May 2023
Line 20:		Line 20:
	: Date de intrare valide		: Date de intrare valide
	: 18		: 18
	==Explicație==		==Explicație exemplu==
	Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.		Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.

Line 55:		Line 55:


	~~def main() -> None~~:		if __name__ == '__main__':
	# Citirea datelor de intrare		# Citirea datelor de intrare
	N, M = map(int, input().split())		N, M = map(int, input().split())
Line 69:		Line 69:
	result = count_submatrices(N, M, matrix)		result = count_submatrices(N, M, matrix)
	print(result)		print(result)


	~~if __name__ == '__main__':~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

Cata at 06:16, 28 April 2023

2023-04-28T06:16:49Z

← Older revision		Revision as of 06:16, 28 April 2023
Line 6:		Line 6:

	==Date de ieșire==		==Date de ieșire==
	Se va afișa un singur număr, reprezentând valoarea cerută.		Se efectuează verificarea, care va afișa un mesaj corespunzător în funcție de input-ul dat și cerințele de validitate ale problemei. Dacă testele de validitate sunt efectuate cu succes, pe un rând nou se va afișa un singur număr, reprezentând valoarea cerută.

	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ N, M ≤ 300		* 1 &les; N, M &les; 300

	==Exemplu==		==Exemplu==
	~~===~~Intrare~~===~~		; Intrare
			: 3 4
	3 4		: ACNN
	ACNN		: NCCA
	NCCA		: AACN
	AACN		; Ieșire
	~~===~~Ieșire~~===~~		: Date de intrare valide
			: 18
	18
	==Explicație==		==Explicație==
	Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.		Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.
Line 64:		Line 64:
	print("Date de intrare invalide")		print("Date de intrare invalide")
	return		return
			else:
			print("Date de intrare valide")
	# Rezolvarea problemei și afișarea rezultatului		# Rezolvarea problemei și afișarea rezultatului
	result = count_submatrices(N, M, matrix)		result = count_submatrices(N, M, matrix)
Line 74:		Line 75:

	</syntaxhighlight>		</syntaxhighlight>
			==Explicație cod==
			Programul are trei funcții principale:

			1. `validate_input`: verifică dacă datele de intrare sunt valide. Verifică dacă N și M se încadrează în intervalul specificat și dacă matricea conține doar caracterele {'A', 'N', 'C'}.

			2. `count_submatrices`: calculează numărul de submatrici ale matricei pentru care numărul de caractere 'A' este egal cu numărul de caractere 'N'. Iterează prin toate submatricile posibile ale matricei și verifică condiția.

			3. `main`: citește datele de intrare, validează datele, rezolvă problema și afișează rezultatul.

			Programul citește N și M de la intrarea standard, apoi citește matricea de dimensiune N x M. Apoi, datele de intrare sunt validate folosind funcția `validate_input`. Dacă datele de intrare sunt valide, programul calculează numărul de submatrici ale matricei pentru care numărul de caractere 'A' este egal cu numărul de caractere 'N', folosind funcția `count_submatrices`. Rezultatul este afișat la ieșirea standard.

Cata: Pagină nouă: ==Cerința== Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. Caracterul 'A' reprezintă o alună, 'N' o nucă, iar 'C' o castană. Dorești să imparți în mod cât mai egal cu sora ta gustările din cameră, iar cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi...

2023-04-19T15:56:21Z

Pagină nouă: ==Cerința== Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. Caracterul 'A' reprezintă o alună, 'N' o nucă, iar 'C' o castană. Dorești să imparți în mod cât mai egal cu sora ta gustările din cameră, iar cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi...

New page

==Cerința==
Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. Caracterul 'A' reprezintă o alună, 'N' o nucă, iar 'C' o castană. Dorești să imparți în mod cât mai egal cu sora ta gustările din cameră, iar cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi câte submatrici cu laturile paralele cu cele ale camerei poți alege, astfel încât numărul de alune să fie egal cu numărul de nuci.

==Date de intrare==
Prima linie din input conține numerele N și M. Pe următoarele N linii se vor găsi câte M caractere din mulțime {'A', 'N', 'C'}, reprezentând elementele matricii.

==Date de ieșire==
Se va afișa un singur număr, reprezentând valoarea cerută.

==Restricții și precizări==
* 1 ≤ N, M ≤ 300
==Exemplu==
===Intrare===

3 4
ACNN
NCCA
AACN
===Ieșire===

18
==Explicație==
Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.

==Rezolvare==
<syntaxhighlight lang="python">
from typing import List

def validate_input(N: int, M: int, matrix: List[List[str]]) -> bool:
# Verifică dacă N și M sunt în intervalul specificat
if not (1 <= N <= 300) or not (1 <= M <= 300):
return False
# Verifică dacă matricea conține doar caracterele {'A', 'N', 'C'}
for i in range(N):
for j in range(M):
if matrix[i][j] not in {'A', 'N', 'C'}:
return False
return True

def count_submatrices(N: int, M: int, matrix: List[List[str]]) -> int:
count = 0
# Iterează prin toate submatricile posibile ale matricei
for i in range(N):
for j in range(M):
for k in range(i, N):
for l in range(j, M):
# Calculează numărul de alune și nuci în submatrice
num_almonds = sum(matrix[p][q] == 'A' for p in range(i, k+1) for q in range(j, l+1))
num_walnuts = sum(matrix[p][q] == 'N' for p in range(i, k+1) for q in range(j, l+1))
# Verifică dacă numărul de alune este egal cu numărul de nuci
if num_almonds == num_walnuts:
count += 1
return count

def main() -> None:
# Citirea datelor de intrare
N, M = map(int, input().split())
matrix = [list(input().strip()) for _ in range(N)]

# Validarea datelor de intrare
if not validate_input(N, M, matrix):
print("Date de intrare invalide")
return

# Rezolvarea problemei și afișarea rezultatului
result = count_submatrices(N, M, matrix)
print(result)

if __name__ == '__main__':
main()

</syntaxhighlight>