partitie

Partitie

== include(page="template/taskheader" task_id="partitie") ==

Fie o multime finita $M$. Se numeste partitie a multimii $M$ un set de submultimi {$S{~1~}$}, {$S{~2~}$}... {$S{~K~}$} cu proprietatile:

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$, diferenta (in modul) dintre oricare $2$ elemente din {$S{~i~}$} este mai mare sau egala cu $D$.

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$ contine pe prima linie numarele naturale $N$ si $D$. Fiecare din urmatoarele $N$ linii contine cate un numar, indicand un element al multimii $M$.

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

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|250000|300000|

|11|50|1014|5950|20000|67901|150099|195993|269956|300000|

h2. Exemplu

== include(page="template/taskfooter" task_id="partitie") ==

2598