Fişierul intrare/ieşire:partitie.in, partitie.outSursăpreONI 2008 Runda 3
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.175 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/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:
T1T2T3T4T5T6T7T8T9T10
1150101459502000067901150099195993269956300000

Exemplu

partitie.inpartitie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content