== include(page="template/taskheader" task_id="scadere") ==
Fie n un număr natural nenul.
Fie $n$ un număr natural nenul.
Să considerăm o expresie de forma: ${@x[1]-x[2]-x[3]-...-x[n]@}$
Să considerăm o expresie de forma: *x[~1~]* - *x[~2~]* - *x[~3~]* - ... - *x[~n~]*
Se știe că scăderea nu este o operație asociativă, adică {@x[1]-(x[2]-x[3])@}$≠${@(x[1]-x[2])-x[3]@}.
Se știe că scăderea nu este o operație asociativă, adică *x[~1~]* - ([*x[~2~]*] - *x[~3~]*) ≠ ([*x[~1~]*] - *x[~2~]*) - *x[~3~]*.
Ca urmare, prin plasarea unor perechi de paranteze în expresie, putem obține diferite valori.
Pentru problema noastră, vom denumi scădere o expresie de forma de mai sus în care pot apărea și paranteze rotunde care se închid corect. Valoarea unei scăderi se obține efectuând operațiile de scădere în ordine de la stânga la dreapta; dacă apar paranteze, se efectuează mai întâi operațiile din paranteze.
h2. Cerință
Date fiind valorile ${@x[1], x[2], …, x[n]@}$ care intervin în scădere, scrieți un program care să rezolve următoarele două cerințe:
Date fiind valorile *x[~1~]*, *x[~2~]*, …, *x[~n~]* care intervin în scădere, scrieți un program care să rezolve următoarele două cerințe:
# să se determine valoarea maximă a unei scăderi (obținută prin inserarea convenabilă a unor paranteze rotunde în expresia {@x[1]-x[2]-x[3]-...-x[n]@}), precum și o scădere având valoare maximă.
# să se determine valoarea maximă a unei scăderi (obținută prin inserarea convenabilă a unor paranteze rotunde în expresia *x[~1~]* - *x[~2~]* - *x[~3~]* - ... - *x[~n~]*), precum și o scădere având valoare maximă.
# să se determine valoarea unei scăderi specificate.
h2. Date de intrare
Fișierul de intrare $scadere.in$ ...
Fișierul de intrare $scadere.in$ conține pe prima linie un număr natural *c* indicând cerința care trebuie să fie rezolvată (1 sau 2). Pe a doua linie este scris numărul natural *n*, care reprezintă numărul de variabile care intervin în scădere. Variabilele sunt numerotate de la 1 la *n* în ordinea în care intervin în scădere. Pe următoarele *n* linii sunt scrise în ordine valorile variabilelor *x[~1~]*, *x[~2~]*, …, *x[~n~]*, câte o valoare pe o linie. Dacă cerința este 2, fișierul mai conține o linie pe care este scris un șir de caractere reprezentând o scădere.
h2. Date de ieșire
În fișierul de ieșire $scadere.out$ ...
Fișierul de ieșire $scadere.out$ va conține pentru [*c*]=1 două linii; pe prima linie va fi scris un număr întreg reprezentând valoarea maximă a unei scăderi (obținută prin inserarea convenabilă a unor paranteze rotunde în expresia *x[~1~]* - *x[~2~]* - *x[~3~]* - ... - *x[~n~]*), iar pe a doua linie o scădere având valoare maximă. Dacă [*c*]=2 fișierul de ieșire va conține o singură linie pe care va fi scris un număr întreg reprezentând valoarea scăderii specificate pe ultima linie a fișierului de intrare.
h2. Restricții
* $... < ... ≤ ...$
h2. Exemplu
* 3 ≤ *n* ≤ 5000
* Valorile variabilelor *x[~1~]*, *x[~2~]*, …, *x[~n~]* sunt numere întregi din intervalul [-100, 100].
* Scăderea din fișierul de intrare, respectiv scăderea de valoare maximă afișată în fișierul de ieșire vor avea maxim 40000 de caractere care pot fi doar cifre, litera mică 'x', paranteze rotunde și operatorul '-' (minus).
* Pentru teste valorând 50% din punctaj cerința va fi 1. Pentru afișarea corectă a valorii maxime se acordă 40% din punctajul pe test. Punctajul integral se acordă pentru afișarea corectă a valorii maxime și a unei scăderi de valoare maximă.
table(example).
|_. scadere.in |_. scadere.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
h2. Exemplu
...
table(example).
|_. scadere.in |_. scadere.out |_. Explicații |
| 1
4
-7
5
-10
19
| 17
x1-x2-(x3-x4)
| Parantezarea care conduce la valoarea maximă este:
*x[~1~]* - *x[~2~]* - ([*x[~3~]*] - *x[~4~]*) = -7 - 5 - (-10 - 19) = -12 - (-29) = -12 + 29 = 17
|
| 2
4
-7
5
-10
19
x1-((x2-x3)-x4)
| -3
| *x[~1~]* - (([*x[~2~]*] - *x[~3~]*) - *x[~4~]*) = -7 - ((5 - (-10)) - 19) = -7 - (15 - 19) = -7 - (-4) = -7 + 4 = -3
|
== include(page="template/taskfooter" task_id="scadere") ==
