.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » scadere

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
scadere


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

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 variabilelor x1, x2, ..., xn care intervin în scădere, scrieţi un program care să rezolve următoarele două cerinţe:
1. 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ă.
2. 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ă.

Exemple

scadere.inscadere.outExplicaţ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

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIG 2015: cript, tv1, nebuni, spioni1, ssk, magic7, restaurare, sort2dist, echer, lightbot, teren1, iepuras1, inventie
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, nebuni, castig, expand, wb, prime2, virgule, b210
Despre şiruri de caractere: scp, ab, sl, nrcuv, rv, kpal, chimie, reteta, replace, grad, index, cod, text, decript, spam, complex, cifre, anagrame, balbe, criptmat, mesaj, maxim, astre, sablon, formule, ed, balls, vocale, prop, bacan, novel, bitslang, text2, ref, scor2, convert, cod2, compress, pstring, sub, rima, program1, sms, circular, randuri, cezar, bifo, joc9, pal, bare, joc12, fractie, cod3, tunel, csir, top, ratina, cifru1, limbaj, adun, ecuatii, dir, paritate, virus, sir6, mesaj2, text1, sirul, ogorul, rez, sablon1, anag, sir8, seti, secvsir, dp, cuvant, strings, antipatie, fractie1, links, ordonare, text3, concat, codif, cheie, alfabetar, cuvinte2, comp, litere, mxl, mesaj3, expresie2, grad2, antic, zuma, expeval, combcuv, lgdrum, subtitrare, compresie, zigzag, azeval, fraze, subsecvente, showroom, rebus1, agenda, opmult, betisoare, reziston, clase, vot2, ecp, smiley, charlie, cript, spioni1, sablon3, expand, culori3, virgule
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, barci
Software recomandat
Chestionare recomandate
surse trimise | ajutor