3438 - Triunghi 5 - Revision history

RaulOtet: Pagină nouă: Se consideră `A` un tablou bidimensional cu `n` linii, `n` coloane și elemente numere naturale. O zonă triunghiulară a tabloului, reprezentată de tripletul `(lin, col, k)`, este o zonă de forma unui triunghi dreptunghic cu catetele de lungime egală cu `|k|`, definită astfel: # Pentru `k>0`, zona este compusă din `k` linii: #* pe prima linie a zonei se află elementele A[lin][col] 2024-07-28T08:58:29Z Pagină nouă: Se consideră <code>A</code> un tablou bidimensional cu <code>n</code> linii, <code>n</code> coloane și elemente numere naturale. O zonă triunghiulară a tabloului, reprezentată de tripletul <code>(lin, col, k)</code>, este o zonă de forma unui triunghi dreptunghic cu catetele de lungime egală cu <code>|k|</code>, definită astfel: # Pentru <code>k>0</code>, zona este compusă din <code>k</code> linii: #* pe prima linie a zonei se află elementele <code>A[lin][col]</cod... New page Se consideră <code>A</code> un tablou bidimensional cu <code>n</code> linii, <code>n</code> coloane și elemente numere naturale. O zonă triunghiulară a tabloului, reprezentată de tripletul <code>(lin, col, k)</code>, este o zonă de forma unui triunghi dreptunghic cu catetele de lungime egală cu <code>|k|</code>, definită astfel: # Pentru <code>k>0</code>, zona este compusă din <code>k</code> linii: #* pe prima linie a zonei se află elementele <code>A[lin][col]</code>, <code>A[lin][col+1]</code>, …, <code>A[lin][col+k-1]</code>; #* pe a doua linie a zonei se află elementele <code>A[lin+1][col]</code>, <code>A[lin+1][col+1]</code>, …, <code>A[lin+1][col+k-2]</code>; #* pe a treia linie a zonei se află elementele <code>A[lin+2][col]</code>, <code>A[lin+2][col+1]</code>, …, <code>A[lin+2][col+k-3]</code>; #* … #* pe ultima linie a zonei se află elementul <code>A[lin+k-1][col]</code>. # Pentru <code>k<0</code>, zona este compusă din <code>|k|=-k</code> linii: #* pe prima linie a zonei se află elementul <code>A[lin-|k|+1][col]</code>; #* pe a doua linie a zonei se află elementele <code>A[lin-|k|+2][col-1]</code>, <code>A[lin-|k|+2][col]</code>; #* … #* pe ultima linie a zonei se află elementele <code>A[lin][col-|k|+1]</code>, <code>A[lin][col-|k|+2]</code>,…, <code>A[lin][col]</code>. Suma elementelor ce compun o zonă triunghiulară se numește suma zonei. = Cerința = Scrieţi un program care, cunoscând tabloul <code>A</code> şi <code>Q</code> zone triunghiulare, determină cea mai mare dintre sumele zonelor. = Date de intrare = Fișierul de intrare <code>triunghi.in</code> conține pe prima linie numărul natural <code>n</code>, cu semnificaţia din enunţ. Pe următoarele <code>n</code> linii se găsesc câte n valori naturale, reprezentând elementele tabloului <code>A</code>. Pe linia <code>n+2</code> se află numărul natural <code>Q</code>, reprezentând numărul zonelor triunghiulare. Pe următoarele <code>Q</code> linii se găsesc tripletele de valori <code>lin col k</code>, care reprezintă cele <code>Q</code> zone, în forma descrisă în enunţ. Valorile aflate pe aceeaşi linie a fişierului sunt separate prin câte un spațiu. = Date de ieșire = Fișierul de ieșire <code>triunghi.out</code> va conține o singură linie pe care va fi scris un număr natural reprezentând suma maximă cerută. = Restricții și precizări = * <code>3 ≤ n ≤ 1000</code>; <code>1 ≤ Q ≤ 100000</code>; <code>2 ≤ |k| ≤ n</code> * Valorile din tablou sunt numere naturale din intervalul <code>[1,100]</code>. * Liniile şi coloanele tabloului <code>A</code> sunt numerotate de la <code>1</code> la <code>n</code> (liniile de sus în jos, iar coloanele de la stânga la dreapta). * <code>|k|</code> reprezintă modulul numărului <code>k</code> (<code>k</code>, pentru <code>k≥0</code>, respectiv <code>-k</code>, pentru <code>k<0</code>). * Se garantează că orice zonă triunghiulară dintre cele <code>Q</code> este complet inclusă în tabloul <code>A</code>. = Exemplu: = <code>triunghi.in</code> 6 5 8 10 4 9 4 2 10 10 2 4 8 8 10 3 4 6 6 4 6 9 7 1 9 6 7 2 2 10 6 10 4 6 1 10 4 3 4 1 3 4 4 -4 6 5 -2 <code>triunghi.out</code> 59 === Explicație === Zona triunghiulară de sumă maximă (<code>59</code>) este reprezentată de tripletul <code>(4 4 -4)</code> și conține valorile evienţiate: <code>59=4+(10+2)+(10+3+4)+(4+6+9+7)</code>. <syntaxhighlight lang="python" line="1"> def suma_zona_triunghiulara(A, lin, col, k): suma = 0 n = len(A) if k > 0: # Zona triunghiulară pentru k > 0 for i in range(k): for j in range(k - i): suma += A[lin + i][col + j] else: # Zona triunghiulară pentru k < 0 k = -k for i in range(k): for j in range(i + 1): suma += A[lin - i + (k - 1)][col - j + (k - 1)] return suma def cea_mai_mare_suma(A, interogari): max_suma = float('-inf') for (lin, col, k) in interogari: suma = suma_zona_triunghiulara(A, lin, col, k) if suma > max_suma: max_suma = suma return max_suma # Citire date n = int(input()) A = [list(map(int, input().split())) for _ in range(n)] Q = int(input()) interogari = [tuple(map(int, input().split())) for _ in range(Q)] # Calculare cea mai mare sumă result = cea_mai_mare_suma(A, interogari) print(result) </syntaxhighlight>