Fişierul intrare/ieşire:procol.in, procol.outSursăAlgoritmiada 2016 Runda 3 Juniori
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 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.

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

procol.inprocol.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?