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

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


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

Gigel a primit de la Moş Crăciun un joc. Jocul are o cutie formată din 2*N căsuţe, dispuse sub forma unei matrice cu două linii şi N coloane. În fiecare căsuţă poate fi plasat un singur jeton pe care este scris un număr întreg nenul din intervalul [-10, 10].
În figura de mai jos este ilustrată configuraţia unei cutii pentru N=7:



Unele dintre căsuţe pot rămâne goale şi nu este obligatoriu ca numărul de jetoane plasate în căsuţele de pe prima linie să fie acelaşi cu numărul de jetoane plasate în căsuţele de pe a doua linie.
Valoarea cutiei se calculează însumând produsele obţinute prin înmulţirea fiecărui număr de pe prima linie cu numărul corespunzător de pe cea de a doua linie (valoarea unei căsuţe goale fiind 0).
De exemplu, pentru cutia din figura de mai sus valoarea este:
6(=(-3)*(0) + (-1)*(-3) + (-2)*(2) + (0)*(4) + (5)*(0) +(-1)*(5) + (0)*(-2)).
Jetoanele pot fi mutate la stânga sau la dreapta pe linia lor din cutie respectând următoarele reguli:
1. la orice moment în orice căsuţă se află un singur jeton;
2. la orice moment ordinea jetoanelor de pe aceeaşi linie se păstrează.
Prin astfel de deplasări de jetoane se pot obţine diferite valori pentru cutie.
De exemplu făcând următoarele deplasări:
1. jetonul -1 de pe linia 1 coloana 6 este mutat în coloana 7
2. jetonul 5 de pe linia 1 coloana 5 este mutat în coloana 6
3. jetonul -3 de pe linia 2 coloana 2 este mutat în coloana 1
4. jetonul 4 de pe linia 2 coloana 4 este mutat în coloana 5
5. jetonul 2 de pe linia 2 coloana 3 este mutat în coloana 4
se obţine următoare amplasare a jetoanelor în cutie:



Valoarea cutiei în acest caz este 36=9+25+2 (şi este maximă posibil).
Scopul jocului este de a deplasa jetoanele din cutie astfel încât cutia să aibă o valoare cât mai mare.

Cerinţă

Scrieţi un program care determină valoarea maximă care se poate obţine pentru o configuraţie a cutiei dată, deplasând jetoanele din cutie după regulile de mai sus.

Date de intrare

Fişierul de intrare cutie2.in conţine pe numărul natural N, reprezentând numărul de coloane ale cutiei. Pe următoarele două linii este descrisă configuraţia cutiei. Pe fiecare dintre cele două linii sunt scrise N numere întregi separate prin spaţiu (0 semnificând o căsuţă goală, iar un număr nenul reprezentând numărul scris pe jetonul din căsuţă corespunzătoare).

Date de ieşire

Fişierul de ieşire cutie2.out va conţine o singură linie pe care va fi scrisă valoarea maximă care se poate obţine pentru configuraţia cutiei dată, deplasând jetoanele din cutie după regulile de mai sus.

Restricţii

1 ≤ N ≤ 200

Exemple

cutie2.incutie2.out
7 -3 -1 -2 0 5 -1 0 0 -3 2 4 0 5 -2 36

autor: Prof. Marinel Şerban
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2007: bitslang, kfactor, np, stalpi, bete, hperm, nr2
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
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, 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