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

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


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

Se ştie că un subşir al unui şir se obţine eliminând zero, unul, sau mai multe elemente din şirul iniţial. Un subşir comun a două şiruri este subşir atât pentru primul, cât şi pentru al doilea şir.

Să considerăm două şiruri de numere naturale x = x1, x2, ..., xM şi y = y1, y2, ..., yN care au cel puţin un subşir comun. Printre subşirurile comune există cel puţin unul maximal. De exemplu, şirurile 5,3,2 şi 7,3,5,2 au trei subşiruri comune maximale: primul este 5, 2, al doilea 3,2, iar al treilea este 5, 3. Pentru fiecare subşir comun maximal s = s1, s2, ..., sk calculăm costul subşirului astfel: pentru fiecare element si (1 <= i <= k) cost(si) = si *|pi – qi|, unde pi şi qi sunt poziţiile unde se află si în şirurile x şi respectiv y, iar |pi – qi| este valoarea absolută a diferenţei pi – qi. Costul subşirului maximal este suma costurilor elementelor subşirului, deci cost(s) = cost(s1) + cost(s2) + ... + cost(sk). Pentru exemplul de mai sus, subşirul 5, 2 are costul 5 * |3 - 1| + 2 * |4 - 3| = 12.

Cerinţă

Să se determine costul minim al unui subşir comun maximal.

Date de intrare

Fişierul de intrare comun.in conţine pe prima linie, separate printr-un spaţiu, numerele naturale M şi N, reprezentând lungimile celor două şiruri. Pe linia a doua se află M numere separate prin câte un spaţiu, reprezentând elementele primului şir. Pe linia a treia se află N numere separate prin câte un spaţiu reprezentând elementele celui de-al doilea şir.

Date de ieşire

Fisierul de iesire comun.out va conţine o singură linie, pe care va fi scris un singur număr natural reprezentând costul minim al unui subşir comun maximal.

Restricţii

  • 3 <= M, N <= 90
  • Elementele celor două şiruri sunt numere naturale cuprinse între 1 şi 100
  • Cele două şiruri conţin cel puţin un subşir comun nevid

Exemple

comun.in comun.out Explicaţii
3 4
5 3 2
7 3 5 2
2

Sunt doua subşiruri comune maximale:
5, 2 având costul 5 * |3 - 1| + 2 * |4 - 3| = 12
3, 2 având costul 3 * |2 – 2| + 2 * |4 – 3| = 2

Costul minim este 2.

comun.in comun.out Explicaţii
6 7
1 2 3 5 4 9
4 1 4 3 2 7 9
13

Sunt 3 subşiruri maximale:
1, 2, 9 având costul 1*1 + 2*3 + 9*1 = 16
1, 3, 9 având costul 1*1 + 3*1 + 9*1 = 13
1, 4, 9 având costul 1*1 + 4*2 + 9*1 = 18

Costul minim este 13 şi aparţine celui de-al doilea subşir.

prof. Dan Pracsiu
Grup Scolar „Stefan Procopiu” Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2008: celule, premii, cai, scp, forum, vedete, film, finala, ab, nice, supertri, mod3, degrade, fractii, balanta, inginer, camp, ozn, hora, trei, rebus, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, barfa, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: cai, rebus, harta, axa, sir, ocean14, reduceri, 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, 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, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor