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...
Consideram permutare BR: bit reverse.
Un sir de lungime 2^k este BR-permutare daca si numai daca este egal cu el insusi dupa ce se aplica BR.
Se da un sir de caractere de lungime N, indexat de la 0. Sirul de caractere S(i, j) este sirul de caractere de lungime 2j ce incepe pe pozitia i, daca el exista. Functia brperm(i, j) este 1 daca S(i, j) exista si este BR-permutare, iar 0 altfel. In aceasta problema se cere sa calculati eficient functia brperm.
Se vrea problema cu manager la RMI. Acolo vom da cu "implementati void init(string s); si bool brperm(int, int).
Date de intrare
Fişierul de intrare brperm.in contine un rand, cu sirul de caractere dat.
Date de ieşire
Definim R(x) ca suma din brperm(i, j) * x20i + j mod 1.000.000.007 pentru i de la 0 la N - 1 si j de la 0 la 19.
În fişierul de ieşire brperm.out se afiseaza R(2) R(3) R(5).
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
...
