RSS Feed
Precedenta

Problema 150

13 Aprilie 2007

Caută într-o matrice triunghiulară un subtriunghi care are suma minimă


Într-o matrice triunghiulară cu numere întregi pozitive și negative vrem să găsim un subtriunghi astfel încât suma numerelor care le conține e minimă.

În exemplul de mai jos, se poate verifica cu ușurință că triunghiul marcat satisface această condiție, având suma −42.

Vrem să facem o astfel de matrice triunghiulară cu 1000 de rânduri, așa că generăm 500500 de numere pseudo-aleatorii sk în intervalul ±219, folosind un tip de generator de numere aleatorii (cunoscut ca Generator Congruent Liniar) în felul următor:

t := 0
de la k = 1 pana la k = 500500:
    t := (615949*t + 797807) modulo 220
    sk := t−219

Deci: s1 = 273519, s2 = −153582, s3 = 450905 etc

Prin urmare, matricea triunghiulara este formata in urmatorul fel:

s1
s2  s3
s4  s5  s6 
s7  s8  s9  s10
...

Un subtriunghi poate începe de la oricare element al matricii, mergțând în jos câte rânduri dorim (incluzând cele 2 elemente din rândul de sub acel element, cele 3 elemente din rândul de sub acele 2 elemente și așa mai departe).
"Suma unui subtriunghi" e definită ca suma tuturor elementelor care le conține.
Găsește suma minimă a unui subtriunghi din matricea generată mai sus.


Tag-uri:

>> Vezi problema originală <<