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

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


Timp maxim de execuţie/test:
2.2 secunde
Memorie totala disponibilă/stivă:
6 MB/1 MB

La un concurs de pariuri se prezintă N candidaţi, care se aşază în şir indian în ordinea înscrierii. Fiecare concurent i deţine o sumă de bani a[i] şi primeşte credit încă a[i], deci poate paria dublul sumei pe care o are. Fiind lacomi, concurenţii vor paria de fiecare dată suma plus creditul. Deşi este informaţie secretă, managerul de concurs află valorile acestor sume.
Desemnarea câştigătorului se face în N-1 etape. În fiecare etapă are loc o singură întâlnire, între doi candidaţi vecini. La toate etapele managerul desemnează, dintre concurenţii rămaşi în concurs pe cei doi care se vor întrece. Lupta dintre doi candidaţi este simplă, fiecare dintre ei pariază şi ridică miza cât mai mult. Câştigă cel care mizează valoarea maximă. Câştigătorul etapei îşi creşte suma cu valoarea pariată de cel care a pierdut. Jucătorul câştigător se retrage pe poziţia avută anterior. Cel care pierde iese din concurs. În caz de mize maxime egale câştigătorul este hotărât, prin tragere la sorţi. Regulamentul concursului spune că la final ultimul concurent rămas este câştigătorul concursului şi pleacă acasă cu suma câştigată. Din motive de publicitate, managerul de concurs doreşte să facă în aşa fel încât la final suma câştigată să fie maximă. El poate influenţa acest maxim prin modul cum alege, în fiecare etapă, pe cei doi candidaţi care se întrec.

Cerinţă

Scrieţi un program care să determine suma maximă care poate fi câştigată la concurs.

Date de intrare

Fişierul de intrare pariuri.in conţine pe prima linie numărul natural N, iar pe linia a doua N numere naturale nenule care reprezintă sumele concurenţilor, numerele fiind separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire pariuri.out va conţine o singură linie pe care va fi scrisă suma maximă care poate fi câştigată la concurs.

Restricţii

  • 2 <= N <= 800
  • 1 <= a[i] <= 100 000, pentru 1<=i<=N

Exemple

pariuri.in pariuri.out Explicaţie
5
1 5 4 3 2

29
a=(1,5,4,3,2)
La etapa 1 concurează jucătorii 1 şi 2.
ştigător este 2 şi se obţine a=(0,7,4,3,2)
La etapa 2 concurează jucătorii 4 şi 5.
ştigător este 4 şi se obţine a=(0,7,4,7,0)
La etapa 3 concurează jucătorii 2 şi 3.
ştigător este 2 şi se obţine a=(0,15,0,7,0)
La etapa 4 concurează jucătorii 2 şi 4.
ştigător este 2 şi se obţine a=(0,29,0,0,0)
Jucătorii marcaţi în vectorul a cu 0 sunt jucătorii eliminaţi.
prof. Ionel-Vasile Piţ-Rada
Colegiul Naţional "Traian" Drobeta Turnu Severin
pitrada@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la InfoOltenia 2014: interclasare, palindromuri, bus, dreapta, riglef
De acelaşi autor: ape, neconex, sstabil, riglef, tg, fence
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, 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, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor