Lista de probleme 2

Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.

Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.

GM are un şir de N numere naturale a1 , a2 ,…, aN , cu proprietatea ai ≤ ai+1 ≤ 2*ai pentru orice i, 1 ≤i < N. El doreşte să scrie în faţa fiecărei valori din şir un semn + sau - astfel încât valoarea S a expresiei obţinute să aibă proprietatea 0 ≤ S ≤ a1 .

Scrieţi un program care să-l ajute pe GM să determine un mod de a scrie cele N semne.