3876 - sum max min - Revision history

Danciu: Pagină nouă: = Cerința = Se dă un șir de `N` numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă `D` egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor `D` ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg `T` dat modulo . = Date de intrare = Programul citește de la tastatură numerele `N` și T 2024-06-04T08:30:38Z Pagină nouă: = Cerința = Se dă un șir de <code>N</code> numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă <code>D</code> egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor <code>D</code> ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg <code>T</code> dat modulo . = Date de intrare = Programul citește de la tastatură numerele <code>N</code> și <code>T</cod... New page = Cerința = Se dă un șir de <code>N</code> numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă <code>D</code> egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor <code>D</code> ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg <code>T</code> dat modulo . = Date de intrare = Programul citește de la tastatură numerele <code>N</code> și <code>T</code>, iar apoi <code>N</code> numere întregi, separate prin spații. = Date de ieșire = Programul va afișa pe ecran valoarea cerută în enunț. = Restricții și precizări = * <code>1 ≤ N, T ≤ 1.000.000</code> * cele <code>N</code> numere citite vor fi din intervalul <code>[0, 1.000.000]</code> * se numește subșir al unui șir o succesiune de elemente(nu neapărat consecutive în acesta) ale acestuia, considerate în ordinea în care apar în șir * pentru teste în valoare de <code>20</code> de puncte <code>N ≤ 20</code> = Exemplu: = Intrare 5 2 1 7 2 3 4 Ieșire 11 === Explicație === Dacă considerăm șirul indexat de la <code>1</code>, un exemplu de subșir ce respectă condiția din enunț este cel format din elementele de pe pozițiile <code>1</code>, <code>3</code> și <code>4</code>, <code>D</code> fiind egal în acest caz cu <code>2</code>, deci egal cu <code>T = 2</code>. Un alt subșir bun este cel format de elementele de pe pozițiile <code>3</code>, respectiv <code>4</code>, <code>D</code> fiind egal în acest caz cu <code>1</code>, deci mai mic decât <code>T = 2</code>. Subșirul format de elementele de pe pozițiile <code>2</code> și <code>3</code> nu respectă condiția din enunț pentru că în cazul acestuia <code>D = 5 > T = 2</code>. Analizând toate subșirurile se obține în final suma <code>11</code>. == Rezolvare == <syntaxhighlight lang="python3"> MOD = 1000000007 def calculate_subarray_sums(n, t, numbers): total_sum = 0 # Initialize total sum for i in range(n): max_so_far = numbers[i] min_so_far = numbers[i] subarray_count = 1 for j in range(i + 1, n): max_so_far = max(max_so_far, numbers[j]) min_so_far = min(min_so_far, numbers[j]) difference = max_so_far - min_so_far if difference <= t: contribution = (subarray_count * difference) % MOD total_sum = (total_sum + contribution) % MOD subarray_count += 1 return total_sum def main(): n, t = map(int, input().split()) numbers = list(map(int, input().split())) subarray_sum = calculate_subarray_sums(n, t, numbers) print(subarray_sum) if name == "main": main() </syntaxhighlight>