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

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


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

Să considerăm două propoziţii formate din cuvinte scrise cu litere mari ale alfabetului englez, oricare două cuvinte consecutive fiind separate de unul sau mai multe spaţii.
Să considerăm c=c1c2...cn şi d=d1d2...dm două cuvinte. Pentru a calcula distanţa dintre cuvintele c şi d, notată dist(c,d), cuvântul mai scurt se completează la sfârşit cu caracterul ′@′ (care are codul ASCII 64), până se obţin două cuvinte de aceeaşi lungime, apoi se calculează suma diferenţelor absolute dintre codurile ASCII ale caracterelor situate în cuvintele c şi d pe poziţii corespondente:
dist(c,d)=|c1-d1|+|c2-d2|+...+|clg-dlg|, unde lg=max{n, m}).
Definim distanţa dintre două propoziţii ca fiind suma distanţelor dintre cuvintele situate în propoziţii pe poziţii corespondente. Dacă una dintre propoziţii are mai puţine cuvinte decât cealaltă se consideră că la sfârşitul acestei propoziţii se află cuvinte vide (cuvinte de lungime 0), până la completarea numărului necesar de cuvinte.
De exemplu, să considerăm propoziţia P1=″ANA ARE MERE″ şi propoziţia P2=″VASILE NU″. Distanţa dintre propoziţia P1 şi propoziţia P2 este:
dist(P1,P2)=dist(″ANA″, ″VASILE″)+dist(″ARE″, ″NU″)+dist(″MERE″,″″).
dist(″ANA″,″VASILE″)=|′A′-′V′|+|′N′-′A′|+|′A′-′S′|+|′@′-′I′|+|′@′-′L′|+|′@′-′E′|=
|65-86|+|78-65|+|65-83|+|64-73|+|64-76|+|64-69|=21+13+18+12+9+5=78
dist(″ARE″,″NU″)=|′A′-′N′|+|′R′-′U′|+|′E′-′@′|=|65-78|+|82-85|+|69-64|=13+3+5=21
dist(″MERE″,″″)=|′M′-′@′|+|′E′-′@′|+|′R′-′@′|+|′E′-′@′|=|77-64|+|69-64|+|82-64|+|69-64|=13+5+18+5=41.

Deci dist(P1,P2)=78+21+41=140
În scopul de a minimiza distanţa dintre cele două propoziţii, asupra celei de a doua propoziţii putem executa una sau mai multe operaţii. O operaţie constă în a muta prima literă dintr-un cuvânt la sfârşitul cuvântului precedent (dacă acesta există) sau ultima literă dintr-un cuvânt la începutul cuvântului următor. Cuvinte vide se pot afla doar la sfârşitul unei propoziţii, nu şi la începutul sau în interiorul ei (nici în propoziţiile date, nici în propoziţiile obţinute în urma aplicării operaţiilor). Cuvintele din propoziţie şi cuvintele obţinute în urma operaţiilor nu pot să depăşească 20 de litere.

Cerinţă

Să se determine distanţa minimă care se poate obţine între cele două propoziţii efectuând operaţii de tipul celor descrise în enunţ. Se cere de asemenea să se determine şi numărul minim de operaţii ce trebuie să fie executate asupra celei de a doua propoziţii pentru a obţine distanţa minimă.

Date de intrare

Fişierul de intrare dist.in conţine pe prima linie prima propoziţie, iar pe cea de a doua linie a doua propoziţie.

Date de ieşire

Fişierul de ieşire dist.out va conţine o singură linie pe care vor fi scrise două numere naturale separate prin spaţiu dmin nrmin, reprezentând în ordine distanţa minimă dintre cele două propoziţii, respectiv numărul minim de operaţii ce trebuie să fie executate asupra celei de a doua propoziţii pentru a obţine distanţa minimă.

Restricţii

Lungimea totală a unei propoziţii nu depăşeşte 500 caractere.
Lungimea maximă a unui cuvânt nu depăşeşte nici în propoziţiile date, nici în propoziţia obţinută în urma aplicării operaţiilor din enunţ 20 de caractere.
Numărul maxim de cuvinte dintr-o propoziţie este 100.
Se acordă 60% din punctaj pentru determinarea distanţei minime şi 100% pentru rezolvarea ambelor cerinţe.

Exemple

dist.indist.outExplicaţii
ANA ARE MERE VASILE NU 62 9 Propoziţia a doua, după aplicarea celor 9 operaţii, este:
V ASI LENU

autor: Prof. Emanuela Cerchez
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, joc6, log, maxq, tric, cover, munte1, promo, puncte1, role
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
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, 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
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, flori2, cntgcd, 2sah, matcnt, nmult
Software recomandat
surse trimise | ajutor