Revizia anterioară Revizia următoare
| 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 oricare din cele 3 cerinte
- 1 ≤ K ≤ 100.000, pentru oricare din cele 3 cerinte
- 1 ≤ C ≤ 1.000.000.000
Exemplu
| procol.in | procol.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
