RSS Feed
Precedenta
Următoarea

Problema 149

13 Aprilie 2007

Caută subșirul care are suma maximă


Privind la tabelul de mai jos, se poate verifica cu ușurință ca suma maximă posibilă a numerelor adiacente în orice direcție (pe orizontală, verticală, diagonală sau anti-diagonală) e 16 (= 8 + 7 + 1).

−2532
9−651
3273
−18−4  8

Să repetăm această căutare, dar pe o scară mult mai largă:

Pentru început, generează 4 milioane de numere pseudo-aleatorii folosind o anumită variantă a unui generator numit "Generator Fibonacci Întârziat":

Pentru 1 ≤ k ≤ 55, sk = [100003 − 200003k + 300007k3] (modulo 1000000) − 500000.
Pentru 56 ≤ k ≤ 4000000, sk = [sk−24 + sk−55 + 1000000] (modulo 1000000) − 500000.

Prin urmare, s10 = −393027 și s100 = 86613.

Termenii lui s sunt apoi aranjați într-un tabel de dimensiune 2000×2000, folosind primele 2000 de numere pentru a umple primul rând (secvențial), următoarele 2000 pentru a umple al doilea rând și așa mai departe.

Pentru final, găsește cea mai mare sumă de (oricâte) numere adiacente în orice direcție (pe orizontală, verticală, diagonală sau anti-diagonală).


Tag-uri:

>> Vezi problema originală <<