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

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


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

Dupã cum stiti, spatiul de memorare pe un hard-disk este partitionat în discuri logice, fiecare partitie (disc logic) având o anumitã dimensiune. La rândul sãu, o partitie este împãrtitã în mai multe zone de dimensiuni egale denumite clustere. Sã considerãm cã discul nostru are N clustere, numerotate de la 1 la N.
Un fisier memorat pe disc poate ocupa unul sau mai multe clustere, nu neapãrat consecutive. Clusterele care nu sunt alocate nici unui fisier se numesc libere.
Pentru a mãri viteza de acces la informatiile de pe disc este de dorit ca toate clusterele care constituie un fisier sã fie consecutive. Din acest motiv, este recomandabil ca o datã la 3-4 luni sã realizati defragmentarea discului. Prin defragmentare, clusterele de pe disc sunt mutate, astfel încât la sfârsitul operatiei de defragmentare, fiecare fisier va ocupa o secventã de clustere consecutive, alocate în ordine (adicã primul cluster din secventã este primul cluster al fisierului, al doilea cluster din secventã este al doilea cluster al fisierului, etc.). Mai exact, fisierul 1 va avea alocate clusterele 1, 2, ..., p1; fisierul 2 va avea alocate clusterele p1+1, p1+2, ..., p1+p2, etc., unde cu pi am notat numãrul de clustere alocate fisierului i.
Utilizatorii de Windows realizeazã defragmentarea cu un program special denumit Disk Defragmenter, dar voi nu aveti acest program, asa cã va trebui sã îl faceti singuri.
Programul vostru poate sã execute operatii de mutare de clustere astfel:
- citeste în memoria internã continutul unui cluster alocat unui fisier;
- scrie continutul clusterului citit într-un alt cluster liber.
Dupã o operatie de mutare clusterul al cãrui continut a fost citit în memorie si apoi scris în celãlalt cluster este declarat liber, iar clusterul în care am scris, evident, devine ocupat (fiind alocat fisierului).
Evident cã programul vostru de defragmentare este considerat eficient dacã el va realiza defragmentarea utilizând un numãr minim de operatii de mutare.

Cerinta
Sã se determine numãrul minim de operatii de mutare necesare pentru defragmentarea unui disc.

Date de intrare
Fisierul de intrare hd.in contine pe prima linie un numãr natural N reprezentând numãrul de clustere de pe disc. Pe cea de a doua linie este scris un numãr natural F reprezentând numãrul de fisiere memorate pe disc. Pe urmãtoarele F linii sunt descrise fisierele, câte un fisier pe o linie. Linia care descrie un fisier începe cu un numãr natural p reprezentând numãrul de clustere alocate fisierului. Urmeazã o succesiune de p numere naturale distincte cuprinse între 1 si N, reprezentând clusterele alocate fisierului, în ordinea în care acestea au fost alocate. Numerele de pe aceeasi linie sunt separate prin spatiu.

Date de iesire
Fisierul de iesire hd.out va contine o singurã linie pe care va fi scris un singur numãr natural, reprezentând numãrul minim de operatii de mutare necesare pentru defragmentarea întregului disc.

Restrictii
0 <= F < N <= 10000
Toate clusterele alocate fisierelor sunt distincte.
Existã cel putin un cluster liber.

Exemplu

hd.in hd.out Explicatie

50
3
4 18 4 7 9
1 20
3 2 3 6

9 Fisierul 1 este format (în ordine) din clusterele 18, 4, 7 si 9 care vor trebui mutate în clusterele 1, 2, 3, respectiv 4.
Fisierul 2 este format dintr-un singur cluster (20) si acesta trebuie mutat în clusterul 5.
Fisierul 3 are clusterele 2, 3 si 6 care trebuie mutate în clusterele 6, 7, 8.
Numãrul minim de mutãri necesare este 9. O solutie posibilã cu 9 mutãri este: 6->8, 2->6, 4->2, 9->4, 18->1, 20->5, 3->9, 7->3, 9->7

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, pajura, pc, sir, cadere, pioni
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, 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, dist, 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 vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Software recomandat
surse trimise | ajutor