== include(page="template/taskheader" task_id="partitie") ==
Poveste si cerinta...
Fie o multime finita $M$. Se numeste partitie a multimii $M$ un set de submultimi {$S{~1~}$}, {$S{~2~}$}... {$S{~K~}$} ({$K ≥ 1$}) cu proprietatile:
* reuniunea celor $K$ submultimi are ca rezultat multimea $M$
* intersectia oricaror doua submultimi distincte este multimea vida
Dandu-se multimea $M$ cu $N$ elemente si numarul natural $D$, sa se determine numarul minim de submultimi in care poate fi partitionata $M$ astfel incat pentru orice submultime {$S{~i~}$} de cardinal cel putin $2$ din partitie, diferenta (in modul) dintre oricare $2$ elemente din {$S{~i~}$} este mai mare sau egala cu $D$.
h2. Date de intrare
Fisierul de intrare $partitie.in$ ...
Fisierul de intrare $partitie.in$ contine pe prima linie numerele naturale $N$ si $D$. Fiecare din urmatoarele $N$ linii contine cate un numar, indicand un element al multimii $M$.
h2. Date de iesire
In fisierul de iesire $partitie.out$ ...
In fisierul de iesire $partitie.out$ se va afisa pe prima linie numarul minim de submultimi dintr-o partitie care indeplineste conditia impusa. Urmatoarele $N$ linii contin impartirea pe submultimi a elementelor multimii $M$. Astfel, linia $i+1$, cu $i$ de la $1$ la $N$, contine numarul submultimii in care este plasat elementul de pe linia $i+1$ din fisierul de intrare. Daca sunt mai multe solutii posibile se va afisa oricare.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $D$ si elementele multimii $M$ sunt numere naturale naturale din intervalul $[1, 10^9^]$
* Punctajul pe un test este obtinut doar daca atat numarul de submultimi cat si impartirea elementelor in submultimi este corecta
* La corectare vor exista 10 teste, fiecare valorand 10 puncte. In tabelul de mai jos se regasesc valorile lui $N$ pentru fiecare test in parte:
table(example). |_. T1 |_. T2 |_. T3 |_. T4 |_. T5 |_. T6 |_. T7 |_. T8 |_. T9 |_. T10 |
|11|50|1014|5950|20000|67901|150099|195993|269956|300000|
h2. Exemplu
table(example). |_. partitie.in |_. partitie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|5 3
9
2
11
5
3
|2
1
1
2
1
2|
h3. Explicatie
...
Submultimea $1$ este {${9, 2, 5}$}, iar submultimea $2$ va fi {${11, 3}$}. Astfel, diferenta dintre oricare doua numere din aceeasi submultime este cel putin $3$. Multimea data nu poate fi partitionata in mai putin de $2$ submultimi astfel incat proprietatea data sa fie respectata.
== include(page="template/taskfooter" task_id="partitie") ==
