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