sali

Sali

În căutare de modalităţi de a obţine bani de buzunar pentru a-ţi face viaţa de student mai plăcută, ai găsit pe un site de anunţuri postul de "ajutor administrator sistem informatic şcoală", la care te-ai şi angajat. Desigur, pe timp de pandemie, ajutarea în administrarea şcolilor este mai dificilă decât pare.

Mai exact, acum se doreşte împărţirea unei clase de $N$ elevi în mai multe săli (de capacitate presupusă infinită) de-a lungul unui coridor lung (presupus infinit), pentru a promova distanţarea socială. Din păcate însă, între cei $N$ elevi există $M$ relaţii de prietenie (bineînţeles, bidirecţionale), iar doi prieteni nu vor fi de acord cu planul de împărţire, decât dacă aceştia vor fi repartizaţi în aceeaşi sală sau, cel mult, în săli adiacente. Mai exact, doi prieteni $i$ şi $j$ nu vor fi de acord dacă şi numai dacă $|s(i) - s(j)| ≤ 1$.

Mai exact, acum se doreşte împărţirea unei clase de $N$ elevi în mai multe săli (de capacitate presupusă infinită) de-a lungul unui coridor lung (presupus infinit), pentru a promova distanţarea socială. Din păcate însă, între cei $N$ elevi există $M$ relaţii de prietenie (bineînţeles, bidirecţionale), iar doi prieteni nu vor fi de acord cu planul de împărţire, decât dacă aceştia vor fi repartizaţi în aceeaşi sală sau, cel mult, în săli adiacente. Mai exact, doi prieteni $i$ şi $j$ vor fi de acord cu planul de împărţire dacă şi numai dacă $|s(i) - s(j)| ≤ 1$ ( $s(i)$ reprezintă indicele sălii la care va fi atribuit elevul cu numărul $i$, iar $|x|$ reprezintă modulul numărului întreg $x$ ).

Pentru a respecta cât mai îndeaproape normele de distanţare socială, trebuie ca elevii să fie repartizaţi în cât mai multe săli.

În fişierul de ieşire $sali.out$ se va regăsi pe prima linie un număr natural $K$, numărul maxim de săli în care pot fi repartizaţi.

Pe a doua linie se vor regăsi $N$ numere naturale din intervalul $1..K$. Al $i$-lea număr va reprezenta indicele sălii atribuite elevului cu numărul $i$.

Pe a doua linie se vor regăsi $N$ numere naturale din intervalul $[1..K]$. Al $i$-lea număr va reprezenta indicele sălii atribuite elevului cu numărul $i$.

h2. Restricţii

1 2 2 4 4 3
|

h3. Explicaţie
 
...
 

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