Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-09-09 14:48:04.
Revizia anterioară Revizia următoare
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 ...
Date de ieşire
În fişierul de ieşire brperm.out se afla un sir binar...
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
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
