Fişierul intrare/ieşire:multimi.in, multimi.outSursăHappy Coding 2007
AutorFlorin ManeaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.3 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/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.inmultimi.out
10
4
8 9 10
4 5 6 7
2 3 6 7 10
1 3 5 7 9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content