Fişierul intrare/ieşire:	procol.in, procol.out	Sursă	Algoritmiada 2016 Runda 3 Juniori
Autor	Eugenie Daniel Posdarascu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.25 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Progresii Colorate

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

Date de intrare

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.

Date de ieşire

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.

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

Exemplu

Cum se trimit solutii?