Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | partitie.in, partitie.out | Sursă | preONI 2008 Runda 3 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Partitie
Fie o multime finita M. Se numeste partitie a multimii M un set de submultimi S1, S2... SK (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 Si de cardinal cel putin 2 din partitie, diferenta (in modul) dintre oricare 2 elemente din Si este mai mare sau egala cu D.
Date de intrare
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.
Date de iesire
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.
Restrictii
- D si elementele multimii M sunt numere naturale naturale din intervalul [1, 109]
- 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:
| T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 | T10 |
|---|---|---|---|---|---|---|---|---|---|
| 11 | 50 | 1014 | 5950 | 20000 | 67901 | 150099 | 195993 | 269956 | 300000 |
Exemplu
| partitie.in | partitie.out |
|---|---|
| 5 3 9 2 11 5 3 | 2 1 1 2 1 2 |
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.
