#3889
CntSubsirMax
Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a
este considerat mai mic în ordine lexicografică decât un șir b
dacă a
este prefix al lui b
, sau dacă există o poziție i
pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] < b[i]
. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exemplu zzxx
pentru azbxazbxaax
). Pentru un șir s
de caractere vom nota cu m(s)
subșirul maxim lexicografic al lui s
, și cu v(s) = |m(s)|
lungimea acestui subșir. Felicia vă dă un șir s
format din caractere mici ale alfabetului englez. Considerați toate subsecvențele continue s'
ale lui s
. Felicia vrea să calculați suma valorilor v(s')
pentru toate subsecvențele posibile s'
amintite anterior
Concursul Național Info Pro, Etapa II
Problema | CntSubsirMax | Operații I/O |
![]() |
---|---|---|---|
Limita timp | 0.1 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
Id soluție | #51566805 | Utilizator | |
Fișier | cntsubsirmax.cpp | Dimensiune | 485 B |
Data încărcării | 12 Iulie 2024, 17:31 | Scor / rezultat | 100 puncte |
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0 secunde | OK. | 10 | 10 | ||
2 | 0 secunde | OK. | 10 | 10 | ||
3 | 0 secunde | OK. | 10 | 10 | ||
4 | 0 secunde | OK. | 10 | 10 | ||
5 | 0 secunde | OK. | 10 | 10 | ||
6 | 0 secunde | OK. | 10 | 10 | ||
7 | 0 secunde | OK. | 10 | 10 | ||
8 | 0.032 secunde | OK. | 10 | 10 | ||
9 | 0.052 secunde | OK. | 10 | 10 | ||
10 | 0.068 secunde | OK. | 10 | 10 | ||
Punctaj total | 100 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema CntSubsirMax face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.