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

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


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

Consideram un sir de N numere naturale distincte x1, x2, ... xN. Vom numi reducere de lungime p eliminarea de la unul dintre cele doua capete ale sirului a secventei formate din primele, respectiv ultimele p elemente din sir. Mai exact, o reducere de lungime p consta fie din eliminarea elementelor x1, x2, ...,xp, fie eliminarea elementelor xN-p+1, xN-p+2, ..., xN. Evident, dupa reducere, sirul devine mai scurt cu p elemente.
Sirului obtinut in urma reducerii i se pot aplica in continuare operatii de reducere de diferite lungimi, procedeul continuand pana cand sir devine vid.
Costul unei reduceri se calculeaza ca fiind diferenta absoluta dintre elementele de la capetele secventei care se elimina inmultita cu numarul de elemente ale secventei. Presupunand ca reducerea este formata din secventa xi, xi+1, ..., xk, atunci costul reducerii este |xi – xk|*(i-k+1). Daca reducerea este de lungime 1, atunci costul sau este dat de valoarea elementului eliminat. Costul total al reducerilor este dat de suma tuturor reducerilor aplicate sirului.

Cerinta

Sa se determine costul total maxim al reducerilor aplicate sirului.

Date de intrare

Fisierul de intrare reduceri.in contine pe prima linie numarul natural N, iar pe urmatoarea linie se afla N numere naturale distincte separate prin cate un spatiu, reprezentand sirul.

Date de iesire

Fisierul reduceri.out va contine o singura linie pe care va fi scris costul total maxim care se poate obtine aplicand reduceri succesive sirului.

Restrictii si precizari

3<=N<=100
Elementele sirului sunt numere naturale distincte si nenule din intervalul 1..1000.
Poate fi aplicata sirului o singura reducere, care consta in eliminarea intregului sir.

Exemplu

reduceri.in

reduceri.out

Explicatii

6
54 29 196 21 133 118

768

Se vor efectua 3 reduceri. Prima reducere: se elimina primele 3 elemente cu un cost de 426. A doua reducere: se elimina ultimul element, cu un cost de 118. Ultima reducere: se elimina ce a ramas din sir, adica 21 si 133, cu un cost de 224. Costul total este 426+118+224=768

prof. Dan Pracsiu
Gr. Sc. Ind. “Stefan Procopiu” Vaslui
Contact: dpracsiu@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2006: scara, programs, nr, iepuras2, numere3, robot2, fry, suma, sah, formule, perm, cifra, repeat, ture, xor, policefm, unu, criptare, ed, bilete, vector, scor, ratb, infinit, race, dragon, kreg, placi, hanoig, red, 2sec, flood, sume3, balls, festival, croco, johnie, matrice3, pavaj, sume, arthur, kimberley, kafka, vocale, pento, prop, ro, sol, bacan, erdos, poligon, druid, novel, gramezi, nrbinar, laser, spair, caravane, cuburi, grup, invest, cd, friends2, mese, toys
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
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, 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, emax, 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