Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | brperm.in, brperm.out | Sursă | RMI 2020 Ziua 1 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Mihai-Cristian Popescu •mihai50000 |
| Timp execuţie pe test | 1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Brperm
SE DA UN ARBORE...
Poveste şi cerinţă...
Am considerat ca sunt date anumite queryuri in input, daca secventa cutare e sau nu br-palindrom. Desigur, putem schimba formatul asta in varianta originala, in caz ca devine inutila schimbarea.
Queryurile sunt doar pe lantul catre radacina - nu vrem lca-uri si alte nebunii
Date de intrare
Fişierul de intrare brperm.in contine pe primul rand numarul N de noduri.
Al doilea rand contine cate N - 1 numere, iar al i-lea este tatal nodului i in arbore (retineti ca nodul 0 este radacina).
Al treilea rand contine un sir de N - 1 caractere, din care al i-lea caracter este caracterul pe muchia dintre i si tatal sau.
Al patrulea rand contine valorile Q A1 U V. Q reprezinta numarul de query-uri, A1 este primul query.
Pentru a determina query-ul Ai+1 dandu-se query-ul Ai si raspunsul R la queryul acesta, se foloseste formula Ai+1 = (Ai + R) * U + V mod N.
Date de ieşire
În fişierul de ieşire brperm.out se afiseaza 3 numere, R(2) R(3) R(5). R(x) este definit ca fiind suma din xjN + i mod 1.000.000.007 pentru fiecare pereche (i, j) pentru care exista un br-palindrom ce se termina pe nodul i, si merge in sus 2j noduri.
Restricţii
- SIGMA = 26
- ... ≤ ... ≤ ...
- Subtask1 (10 puncte): O(Q * N * logN) && NU neaparat linie
- Subtask2 (10 puncte): O(N * logN + Q * N) && NU neaparat linie
- Subtask3 (10 puncte): O(N * logN + Q) && linie && SIGMA = 2 && biased random (comisia a ales, pt fiecare test, cate un numar real p intre 0 si 1 iar fiecare caracter este 'a' cu probabilitate p si 'b' cu probabilitate 1-p)
- Subtask4 (30 puncte): O((N + Q) * logN * logN) sau O((N + Q) * sqrt(N + Q) + Q) (nu cunosc solutie, dar cine stie?) - anulat si inghitit de subtaskul urmator in caz ca nu dam queryuri
- Subtask5 (10 puncte): O(N * logN * logN + Q) - acelasi lucru ca subtaskul urmator daca nu dam queryuri
- Subtask6 (10 puncte): O((N + Q) * logN) - in caz ca exista
- Subtask7 (20 puncte): O(N * logN + Q) - in caz ca exista, altfel punctele merg la ultimul subtask existent
Exemplu
| brperm.in | brperm.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
