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 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, sa se determine numarul minim de submultimi in care poate fi partitionata astfel incat pentru orice submultime Si de cardinal cel putin 2, diferenta (in modul) dintre oricare 2 elemente este mai mare sau egala cu D.
Date de intrare
Fisierul de intrare partitie.in contine pe prima linie numarele naturale N si D, cu semnificatia din enunt. 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......???? Daca sunt mai multe solutii posibile se va afisa oricare.
Restrictii
- 1 ≤ N ≤ 300 000
- D si elementele multimii M sunt numere naturale intregi din intervalul [-109, 109]
Exemplu
| partitie.in | partitie.out |
|---|---|
| 5 3 9 2 11 5 3 | 2 1 1 2 1 2 |
Explicatie
...
