multimi

Multimi

== include(page="template/taskheader" task_id="multimi") ==

Poveste si cerinta...

Consideram multimea $[n]$={${1,...,n}$} a primelor $n$ numere naturale nenule. Multimile $A{~1~},..., A{~m~}$ acopera $[n]$ daca si numai daca oricare ar fi $1 ≤ i ≤ n$ exista $1 ≤ j ≤ m$ astfel incat $A{~j~}$ sa contina pe $i$. Multimile $A{~1~},...,A{~m~}$ separa pe $[n]$ daca si numai daca oricare ar fi $1 ≤ k,p ≤ n$ exista $1 ≤ j ≤ m$ astfel incat cardinalul intersectiei dintre $A{~j~}$ 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 $A{~1~},...,A{~m~}$ sa acopere si sa separe multimea $[n]$. De asemenea sa se afiseze $m$ multimi $A{~1~},...,A{~m~}$ care verifica aceasta proprietate.

h2. Date de intrare

...

In fisierul de intrare $multimi.in$ se gaseste numarul intreg $n$.

h2. 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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 100 000$

h2. Exemplu
table(example). |_. multimi.in |_. multimi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10
|4
8 9 10
4 5 6 7
2 3 6 7 10
1 3 5 7 9

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="multimi") ==

2369