== 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 culoare 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 culoare 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 Daca exista mai multe solutii, afisati oricare. Daca nu exista solutie, afisati $-1$.
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 cerinta $1$
* $1 ≤ K ≤ 100.000$ pentru cerinta $2$
* $1 ≤ N * K ≤ 1.000.000$ pentru cerinta $3$
* $1 ≤ C ≤ 1.000.000.000$ pentru toate cerintele
* Pentru rezolvarea corecta a primei cerinte obtineti *20 de puncte*
* Pentru rezolvarea corecta a celei de a doua cerinte obtineti *30 de puncte*
* Pentru rezolvarea corecta a celei de a treia cerinte obtineti restul de *50 de puncte*
h2. Exemplu
table(example). |_. procol.in |_. procol.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|1
5 3 5
1 3 3
2 4 3
1 5 2
3 4 4
1 1 1
|4|
|2
5 5
1 3 2 1 2
|3093|
|3
5 3 3
|1 1 3
2 3 1
3 3 3
3 1 1
1 2 3|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="procol") ==
