Soluții trimise

Aurel s-a pregătit pentru ninsoare, dar zăpada care s-a așezat aseară tot i-a dat bătăi de cap. Aleea pe care trebuie să o deszăpezească Aurel este formată din 𝑛 dale pătrate, pozițiile acestora fiind numerotate în ordine, de la stânga la dreapta, de la 1 la 𝑛. Fiind un tip meticulos, înainte de a se apuca de treabă, Aurel a determinat cantitatea de zăpadă (exprimată în grame) care s-a așezat pe fiecare dintre cele 𝑛 dale și a notat cu z[𝑖] cantitatea de zăpadă existentă pe dala 𝑖 (1 ≤ 𝑖 ≤ 𝑛). Pentru a curăța aleea, el trebuie să mute toată zăpada de pe alee, în stânga sau în dreapta acesteia. Pentru simplitate, vom considera că zona din stânga aleii are poziția 0, iar zona din dreapta aleii are poziția 𝑛 + 1.

Pentru deszăpezire, Aurel a cumpărat 40 de lopeți speciale, numerotate de la 0 la 39. Cu lopata 𝑘 (0 ≤ 𝑘 ≤ 39) Aurel poate muta cel mult 2𝑘 grame de zăpadă de pe dala pe care se află aceasta pe o poziție alăturată, la stânga sau la dreapta, deci de pe poziția 𝑖 (1 ≤ 𝑖 ≤ 𝑛) pe poziția 𝑖 − 1 sau pe poziția 𝑖 + 1, pentru această acțiune consumând 𝑘 + 1 calorii.

Pentru a fi eficient, Aurel a decis să împartă aleea în două zone. Prima zonă conține toate dalele situate pe poziții mai mici sau egale cu 𝑥, iar a doua zonă conține toate dalele de poziții strict mai mari decât 𝑥. El va folosi lopețile
pentru a muta toată zăpada din prima zonă pe poziția 0 și toată zăpada din a doua zonă pe poziția 𝑛 + 1.

Cunoscând numărul de dale și zăpada acumulată pe fiecare dală, scrieți un program care să rezolve următoarele cerințe:

1. cunoscând valoarea 𝑥, determinați numărul total minim de calorii consumate de Aurel pentru a deszăpezi aleea;
2. determinați valoarea 𝑥 pentru care numărul total de calorii consumate de Aurel pentru deszăpezirea aleii este minim; dacă există mai multe astfel de valori, să se determine cea mai mică dintre acestea.