4044 - camere: Difference between revisions
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... |
No edit summary |
||
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 | * 1 ⩽ N, M ⩽ 300 | ||
==Exemplu== | ==Exemplu== | ||
; Intrare | |||
: 3 4 | |||
: ACNN | |||
: NCCA | |||
: AACN | |||
; Ieșire | |||
: Date de intrare valide | |||
: 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. |
Revision as of 06:16, 28 April 2023
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 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
- 1 ⩽ N, M ⩽ 300
Exemplu
- Intrare
- 3 4
- ACNN
- NCCA
- AACN
- Ieșire
- Date de intrare valide
- 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 else: print("Date de intrare valide") # Rezolvarea problemei și afișarea rezultatului result = count_submatrices(N, M, matrix) print(result)
if __name__ == '__main__':
main()
</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.