Diferențe pentru problema/scadere între reviziile #4 si #3

== 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]@}$

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. Date de intrare

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.

Fișierul de intrare $scadere.in$ ...

h2. Date de ieșire

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.

În fișierul de ieșire $scadere.out$ ...

h2. Restricții

* $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ă.
 

* $... < ... ≤ ...$

h2. Exemplu
table(example).

|_. scadere.in |_. scadere.out |_. Explicații |
| 1
4
-7
5
-10
19
| 17
x1-x2-(x3-x4)

|_. scadere.in |_. scadere.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

|
h3. Explicație