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

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


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

Zăhărel a devenit pasionat de expresii aritmetice. A scris un şir de N numere întregi pe o foaie de hârtie şi se întreabă care este expresia de valoare maximă pe care o poate forma cu aceste numere. El va construi o expresie respectând următoarele restricţii:
1. Ordinea în care apar numerele în şir este aceeaşi cu ordinea în care vor apărea în expresie.
2. Se pot folosi paranteze rotunde şi operatorii +, -, * care vor reprezenta operaţiile de adunare, scădere şi înmulţire. Se consideră că + şi - au aceeaşi prioritate, iar * are cea mai mare prioritate.
3. Operatorii trebuie inseraţi înaintea oricărui element din şir (mai putin înaintea primului element unde, după necesităţi, poate fi introdus doar operatorul -), dar nu este permisă inserarea a doi operatori înaintea aceluiaşi element.
4. Parantezele pot fi aplicate oriunde, respectând condiţia ca expresia rezultată să fie corectă din punct de vedere matematic.

Cerinţă

Scrieţi un program pentru Zăhărel care să determine valoarea maximă a unei expresii pe care o poate construi cu cele N numere din şir.

Date de intrare

Fişierul de intrare emax.in conţine pe prima linie numărul natural N. Pe cea de a doua linie se află N numere întregi separate prin câte un spaţiu reprezentând valorile din şir.

Date de ieşire

Fişierul de ieşire emax.out va conţine un singur număr întreg reprezentând valoarea maximă a unei expresii care se poate construi cu cele N numere din şir, modulo 666013.

Restricţii

1 ≤ N ≤ 100 000
Valorile din şir sunt numere întregi din intervalul [-100,100]

Exemple

emax.inemax.outExplicaţii
4 -1 1 -9 6 108 (-1-1)*(-9)*6 = 108

autor: Mircea Paşoi
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la LOT SV 2007: bcast, cladiri, mesaj1, patrate4, turism, zuzu
De acelaşi autor: copaci, ab2, plimbare, cuvinte, pioni, reinvent, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, turism, puncte1, casute, dep
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor