#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:
k
din șirul S
să se determine lungimea maximă a unei subsecvențe palindromice comune șirurilor X
și Y
.Lot Juniori Magurele, 2016
ID | Utilizator | Problema | Data încărcării | Stare | ||
---|---|---|---|---|---|---|
Dorel | 10 Octombrie 2022, 21:23 | Evaluare finalizată | 100 |