Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | multimi.in, multimi.out | Sursă | Happy Coding 2007 |
| Autor | Florin Manea | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Multimi
Consideram multimea [n]={1,...,n} a primelor n numere naturale nenule. Multimile A1,..., Am acopera [n] daca si numai daca oricare ar fi 1 ≤ i ≤ n exista 1 ≤ j ≤ m astfel incat Aj sa contina pe i. Multimile A1,...,Am separa pe [n] daca si numai daca oricare ar fi 1 ≤ k,p ≤ n exista 1 ≤ j ≤ m astfel incat cardinalul intersectiei dintre Aj si {k,p} sa fie 1 (practic exista cel putin o multime in care nu se afla ambele elemente simultan).
Pentru n dat, sa se gaseasca m minim astfel incat A1,...,Am sa acopere si sa separe multimea [n]. De asemenea sa se afiseze m multimi A1,...,Am care verifica aceasta proprietate.
Date de intrare
In fisierul de intrare multimi.in se gaseste numarul intreg n.
Date de iesire
Pe prima linie a fisierului de iesire multimi.out veti afisa numarul minim m de multimi. Pe urmatoarele m linii veti afisa elementele cate unei multimi. Elementele unei multimi pot fi afisate in orice ordine si trebuie separate intre ele prin cate un spatiu.
Restrictii
- 1 ≤ n ≤ 100 000
Exemplu
| multimi.in | multimi.out |
|---|---|
| 10 | 4 8 9 10 4 5 6 7 2 3 6 7 10 1 3 5 7 9 |
