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

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


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

Discul dur (hard disk) este un dispozitiv utilizat pentru stocarea datelor. Stocarea se face pe o suprafaţă magnetică dispusă pe platane rotunde metalice. Pe un platan, datele sunt organizate în piste şi sectoare, iar zona aflată la intersecţia dintre o pistă şi un sector poartă denumirea de cluster.
Un cluster poate avea două stări: liber, dacă nu conţine date, sau ocupat, atunci când conţine date.
Un platan se numeşte defragmentat dacă toţi clusterii ocupaţi de pe fiecare pistă sunt aşezaţi în ordine consecutivă. Defragmentarea se realizează prin mutarea unor clusteri ocupaţi şi are rolul de a micşora timpul de acces la date. Mutarea unui cluster reprezintă transferul datelor de la un cluster ocupat către un cluster liber de pe aceeaşi pistă.



Cerinţă

Cunoscând numărul de piste P şi de sectoare S al unui platan, numărul şi poziţia clusterilor ocupaţi, să se scrie un program care determină :
1. numărul de piste care au toţi clusterii liberi;
2. numărul minim de mutări de clusteri, pentru fiecare pistă în parte, astfel încât platanul să devină defragmentat.

Date de intrare

Pe prima linie a fişierului de intrare defrag.in se găseşte numărul natural V a cărui valoare poate fi doar 1 sau 2.
Pe a doua linie a fişierului de intrare se găsesc două numere naturale P şi S, separate printr-un spaţiu, cu semnificaţia din enunţ.
A treia linie conţine un număr natural C reprezentând numărul total de clusteri ocupaţi de pe platan, iar pe fiecare dintre următoarele C linii se găseşte câte o pereche de valori pi şi si, 1 ≤ i ≤ C, separate printr-un spaţiu, reprezentând pista, respectiv sectorul unde se află fiecare cluster ocupat.

Date de ieşire

Fişierul de ieşire este defrag.out.
Dacă valoarea lui V este 1 atunci fişierul de ieşire va conţine pe prima linie un număr natural ce reprezintă numărul de piste care au toţi clusterii liberi.
Dacă valoarea lui V este 2 atunci fişierul de ieşire va conţine pe prima linie P numere naturale notate Mi, 1 ≤ i ≤ P, separate prin câte un singur spaţiu, unde Mi reprezintă numărul minim de mutări de clusteri, dintre cei aflaţi pe pista i, astfel încât pe pista i clusterii ocupaţi să se găsească într-o ordine consecutivă.

Restricţii

1 ≤ P ≤ 100
1 ≤ S ≤ 360
1 ≤ C ≤ P*S
• pistele sunt numerotate de la 1 la P începând cu pista exterioară;
• sectoarele sunt numerotate de la 1 la S în sensul acelor de ceasornic începând cu sectorul 1;
• dacă o pistă are toţi clusterii liberi, atunci valoarea cerută la a doua cerinţă este 0;
• 20% din teste vor avea valoarea V = 1, iar 80% din teste vor avea valoarea V = 2.

Exemple

defrag.indefrag.outExplicaţii
1 4 8 10 1 1 1 3 1 5 1 7 4 5 4 1 4 6 4 8 2 2 2 4 1 Datele corespund figurilor anterioare :
V = 1, deci se rezolvă NUMAI prima cerinţă.

• Numărul de piste P = 4 , numărul de sectoare S = 8
• Numărul total de clusteri ocupaţi este C = 10 (cei marcaţi cu negru)
• Pe prima pistă sunt 4 clusteri ocupaţi, în sectoarele 1, 3, 5 si 7.
• Pe a doua pistă sunt 2 clusteri ocupaţi, în sectoarele 2 şi 4.
• Pe a treia pistă nu sunt clusteri ocupaţi.
• Pe a patra pistă sunt 4 clusteri ocupaţi, în sectoarele 1, 5, 6 şi 8.

O singură pistă are toţi clusterii liberi, pista numărul 3, deci valoarea cerută este 1;
2 4 8 10 1 1 1 3 1 5 1 7 4 5 4 1 4 6 4 8 2 2 2 4 2 1 0 1 Datele corespund figurilor anterioare :
V = 2, deci se rezolvă NUMAI a doua cerinţă.

• Pe prima pistă sunt necesare minim două mutări de clusteri pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este 2.
• Pe a doua pistă este suficientă o singură mutare de cluster, pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este 1.
• Pe a treia pistă nu sunt clusteri ocupaţi, deci valoarea cerută este 0.
• Pe a patra pistă este suficientă o singură mutare de cluster, pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este 1.

autor: Prof. Ciprian Cheşcă
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OJI 2015: panda, charlie, ech, lasere, 2sah, dragoni, arc, dominant, pavare1, ordine, covor1, speciale, cuart
De acelaşi autor: patrate1, impozit, neuroni, cern, partitie, vase, poligon4, pegals, xpn, roata, cifreco, 7segmente, clepsidru, amestec, cumpanit, nmult, procente
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, dist, 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, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor