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

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


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

O subsecventa a un sir este formata din niste elemente ale sirului aflate pe pozitii consecutive.
Exemplu: Pentru sirul "1 2 3 4 5 6 7"; "1 2 3", "2 3 4 5 6 7" si "3 4 5" sunt subsecvente, dar "1 3 4" nu este deoarece intre 1 si 3 mai exista si alte elemente (in cazul nostru 2).

Cerinta

Fiind dat un sir A cu numere intregi, se cere sa se gaseasca subsecventa care are modulul sumei minim.

Date de intrare

Pe prima linie a fisierului suma3.in se gaseste numarul N reprezentand lungimea sirului. Pe urmatoarele N linii se afla elementele sirului (cate unul pe fiecare linie).

Date de iesire

Pe prima linie a fisierului suma3.out se vor gasi 3 numere: S I J cu semnificatia: S este numarul cerut (modulul minim al sumei unei subsecvente), I si J sunt capetele subsecventei gasite.

Restrictii

  • N <= 100 000
  • -2 000 000 000 < A[I] < 2 000 000 000
  • I si J trebuie sa respecte urmatoarele conditii: I <= J, modul(A[I]+..+A[J])=S
  • Subsecventele pot avea suma mai mari decat 2 000 000 000
  • Subsecventele pot avea suma mai mici decat -2 000 000 000
  • Se recomanda folosirea unor intregi pe 64 biti
  • Subsecventa din fisierul de iesire trebuie sa contina cel putin un numar
  • Toate numerele sunt intregi
  • S >= 0
  • Daca exista mai multe solutii se va scrie doar una.

Exemple

suma3.in suma3.out
5
1
2
-10
3
4
0 1 5

 

suma3.in suma3.out
9
1000
2
4
8
16
32
64
-127
-2000
1 2 8

 

suma3.in suma3.out
3
1
2
3
1 1 1

Mod de punctare:

Daca modulul sumei este minim atunci se primeste 1 punct. Daca in plus subsecventa gasita este corecta si are modului sumei S atunci se primesc inca 4 puncte (adica 5 in total). Atentie: Daca S este gresit se primesc 0 puncte (chiar daca subsecventa este corecta).

Daniel Dumitran
Universitatea Politehnica Bucuresti

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: traseu, trip, benzina, izo
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, panouri, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
surse trimise | ajutor