procol

Progresii Colorate

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

Poveste şi cerinţă...

Fie $C$ culori numerotate de la $1$ la $C$.
Definim un $k-element$ ca fiind un set de $k$ culori nu neaparat diferite, iar ordinea acestora conteaza. De exemplu, $k-elementul$ $(2 2 1 3)$ este diferit de $(2, 3, 1, 2)$.
O progresie colorata de lungime $N$ reprezinta un set de $N$ k-elemente, cu proprietatea ca oricare $2$ elemente consecutive au cel putin o coloare in comun.
 
Aveti $3$ cerite:
* Cerinta $1$: Dandu-se un vector cu $N$ $k-elemente$, sa se determine lungimea celui mai lung subsir care este progresie colorata.
* Cerinta $2$: Dandu-se un $k-element$ $X$, sa se determine cate alte $k-elemente$ $Y$ ar putea sa apara intr-o progresie colorata imediat dupa elementul $X$. Altfel spus, cate $k-elemente$ exista care au cel putin o coluare in comun cu $k-elementul$ $X$. Deoarece acest numar poate sa fie foarte mare, afisati raspunsul $modulor 666013$
* Cerinta $3$: Sa se afiseze o progresie colorata cu $N$ k-elemente, astfel incat oricare $2$ elemente din aceasta progresie sa fie diferite

h2. Date de intrare

Fişierul de intrare $procol.in$ ...

Fişierul de intrare $procol.in$ va contine pe prima linie un numar natural reprezentand indicele cerintei. Acest numar poate sa fie $1$, $2$ sau $3$. Daca este $1$, pe urmatoarea linie se vor afla $2$ numere $N$, $K$ si $C$. Pe urmatoarele $N$ linii va fi vectorul cu $K-elemente$. Linia $i$ va contine $K-elementul$ $i$, mai exact $K$ culori numerotate de la $1$ la $C$. Daca cerinta este $2$, pe linia $2$ vor fi doar numere $K$ si $C$. Pe urmatoarea linie se va afla $K-elementul$ $X$. Daca cerinta este 3, pe linia $2$ vor fi cele $3$ numere naturale $N$, $K$ si $C$.

h2. Date de ieşire

În fişierul de ieşire $procol.out$ ...

Fişierul de ieşire $procol.out$ va contine raspunsul in functie de cerinta. Daca cerita din input este $1$, trebuie sa afisati un singur numar natural reprezentand lungimea celei mai lungi progresii colorate. Daca cerinta este $2$, trebuie afisat un singur numar natural reprezentand numarul de solutii $modulo 666013$. Daca cerinta este $3$, trebuie sa afisati $N$ linii, pe linia $i$ fiind al $i$-ulea $K-element$ ($K$ numere reprezentand culorile de la $1$ la $C$) din progresia colorata ceruta. Daca nu exista o progresie colorata care sa satisfaca conditia ceruta, afisati $-1$.

h2. Restricţii

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

* $1 ≤ N * K ≤ 200.000$, pentru oricare din cele $3$ cerinte
* $1 ≤ K ≤ 100.000$, pentru oricare din cele $3$ cerinte
* $1 ≤ C ≤ 1.000.000.000$

h2. Exemplu

  multiple lines.
|

h3. Explicaţie
 
...

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