Diferențe pentru problema/defrag între reviziile #1 si #6

Diferențe între titluri:

defrag
Defrag (clasa a 9-a)

Diferențe între conținut:

== include(page="template/taskheader" task_id="defrag") ==
Poveste și cerință...
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ă.
 
!{width:240px}problema/defrag?defrag1.png!
!{width:240px}problema/defrag?defrag2.png!
!{width:240px}problema/defrag?defrag3.png!
 
h2. 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ă:
 
# numărul de piste care au toți clusterii liberi;
# numărul *minim* de mutări de clusteri, pentru fiecare pistă în parte, astfel încât platanul să devină defragmentat.
h2. Date de intrare
Fișierul de intrare $defrag.in$ ...
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 din următoarele $C$ linii se găsește câte o pereche de valori $p[~i~]$ și $s[~i~], 1 ≤ i ≤ C$, separate printr-un spațiu, reprezentând pista, respectiv sectorul unde se află fiecare cluster ocupat.
h2. Date de ieșire
În fișierul de ieșire $defrag.out$ ...
Fișierul de ieșire este $defrag.out$.
h2. Restricții
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 $M[~i~], 1 ≤ i ≤ P$, separate prin câte un singur spațiu, unde $M[~i~]$ 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ă.
h2. Exemplu
h2. Restricții și precizări
table(example).
|_. defrag.in |_. defrag.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* $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$.
h3. Explicație
h2. Exemple
...
table(example).
|_. defrag.in |_. defrag.out |_. Explicație |
| 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$ și [$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$].
|
== include(page="template/taskfooter" task_id="defrag") ==

Nu există diferențe între securitate.