Rezumat problemă

Dorel

#1729

Îl cunoașteți pe Dorel cel ”priceput” la toate. Acesta și-a propus să “strice” armonia unui șir S format din N caractere litere mici ale alfabetului englez, S=(S[1],S[2],…,S[N]).

El alege la întâmplare un caracter din șir, caracter aflat pe poziția k (1≤k≤N) și caută în stânga lui k primul caracter mai mare sau egal cu S[k], fie acesta aflat pe poziția i, S[k]≤S[i]. Dacă acesta nu există, i=1. Această alegere nu este suficientă. Dorel caută în dreapta lui k primul caracter mai mic sau egal cu S[k], fie acesta pe poziția j, S[j]≤S[k]. Dacă acesta nu există, j=N. Extrage din șirul S subșirul astfel delimitat. Ca urmare a alegerii făcute, Dorel obține două subșiruri:

• X=(S[1],S[2],…,S[i-1],S[j+1],S[j+2],…,S[N])
• Y=(S[i],S[i+1],…,S[j])

Cunoscând șirul S, ajutați-l pe Dorel să răspundă la Q întrebări de forma:

• Pentru o poziție k din șirul S să se determine lungimea maximă a unei subsecvențe palindromice comune șirurilor X și Y.

Lot Juniori Magurele, 2016

Fișiere Candale Silviu (silviu) Eugen Nodea concurs

Clasa 10 Şiruri de caractere Probleme diverse

Rezolvă

Detalii

Problema	Dorel	Operații I/O	dorel.in/dorel.out
Limita timp	0.5 secunde	Limita memorie	Total: 128 MB / Stivă 8 MB
Id soluție	#58760903	Utilizator	Raduta Mihail (Mihailraduta)
Fișier	dorel.cpp	Dimensiune	5.78 KB
Data încărcării	03 August 2025, 11:41	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

dorel.cpp: In function 'bool is_palindrome(int, int, const RollingHash&, const RollingHash&)':
dorel.cpp:65:40: error: passing 'const RollingHash' as 'this' argument of 'std::pair<long long int, long long int> RollingHash::get_hash(int, int)' discards qualifiers [-fpermissive]
     auto fwd_hash = rhS.get_hash(p, len);

                                        ^
dorel.cpp:67:47: error: passing 'const RollingHash' as 'this' argument of 'std::pair<long long int, long long int> RollingHash::get_hash(int, int)' discards qualifiers [-fpermissive]
     auto rev_hash = rhRevS.get_hash(rev_p, len);

                                               ^
dorel.cpp: In function 'bool check(int, int, int, const RollingHash&, const RollingHash&)':
dorel.cpp:81:55: error: passing 'const RollingHash' as 'this' argument of 'std::pair<long long int, long long int> RollingHash::get_hash(int, int)' discards qualifiers [-fpermissive]
             pal_hashes_in_Y.insert(rhS.get_hash(p, len));

                                                       ^
dorel.cpp:90:58: error: passing 'const RollingHash' as 'this' argument of 'std::pair<long long int, long long int> RollingHash::get_hash(int, int)' discards qualifiers [-fpermissive]
             if (pal_hashes_in_Y.count(rhS.get_hash(p, len))) {

                                                          ^
dorel.cpp:99:58: error: passing 'const RollingHash' as 'this' argument of 'std::pair<long long int, long long int> RollingHash::get_hash(int, int)' discards qualifiers [-fpermissive]
             if (pal_hashes_in_Y.count(rhS.get_hash(p, len))) {

                                                          ^

Cum funcționează evaluarea?