Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | scadere.in, scadere.out | Sursă | ONI 2015 clasa a 7-a |
|---|---|---|---|
| Autor | Emanuela Cerchez | Adăugată de |
Tinca Matei
•
TincaMatei
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 2048 KB |
| Scorul tău | N/A | Dificultate | N/A |
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Scădere (clasa a 7-a)
Fie n un număr natural nenul.
Să considerăm o expresie de forma: x1 – x2 – x3 – ... – xn
Se știe că scăderea nu este o operație asociativă, adică x1 – (x2 – x3) ≠ (x1 – x2) – x3.
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.
Cerință
Date fiind valorile x1, x2, …, xn 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 x1 – x2 – x3 – ... – xn), precum și o scădere având valoare maximă.
- să se determine valoarea unei scăderi specificate.
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 x1, x2, …, xn, 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.
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 x1 – x2 – x3 – ... – xn), 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.
Restricții
- 3 ≤ n ≤ 5000
- Valorile variabilelor x1, x2, …, xn 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ă.
Exemplu
| scadere.in | scadere.out | Explicații |
|---|---|---|
| 1 4 -7 5 -10 19 |
17 x1-x2-(x3-x4) |
Parantezarea care conduce la valoarea maximă este: x1 – x2 – (x3 – x4) = -7 – 5 – (-10 – 19) = -12 – (-29) = -12 + 29 = 17 |
| 2 4 -7 5 -10 19 x1-((x2-x3)-x4) |
-3 |
x1 – ((x2 – x3) – x4) = -7 – ((5 – (-10)) – 19) = -7 – (15 – 19) = -7 – (-4) = -7 + 4 = -3 |
