Fişierul intrare/ieşire:palsubsecv.in, palsubsecv.outSursăConcursul National de Informatica "Adolescent Grigore Moisil"
AutorFlorin ChiricaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.8 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Palsubsecv

Se da un sir de caractere S de lungime N. Trebuie sa gasim subsirul palindromic al lui S de lungime maxima, cu lungime para. De asemenea avem un buget de B dolarei. Odata ce alegem o solutie, va trebui sa tinem cont de R restrictii care ne vor scadea din buget.
O restrictie de forma (a, b, c) inseamna ca daca este luata subsecventa dintre a si b in palindrom, trebuie sa platim c dolarei. Asta inseamna ca, fiind alese toate pozitiile dintre a si b in palindromul solutie, trebuie sa platim c dolarei.
Care este palindromul par de lungime maxima astfel incat la final sa ramanem cu un numar nenegativ de dolarei?

Date de intrare

Fişierul de intrare palsubsecv.in va contine pe prima linie T, numarul de teste. Pe prima linie a fiecarui test se vor afla trei numere intregi N, R si B, separate prin cate un spatiu. A doua linie va contine sirul S. Urmatoarele R linii ale unui test vor contine fiecare cate trei numere intregi a, b si c, separate prin cate un spatiu, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire palsubsecv.out se vor afla T linii, pe fiecare cate un numar natural care va reprezenta raspunsul la cerinta.

Restricţii

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 33
  • 1 ≤ R ≤ 5.000
  • 1 ≤ B ≤ 109
  • 1 ≤ a ≤ b ≤ N
  • 1 ≤ c ≤ 105
  • S contine doar litere mici ale alfabetului englez
  • x e nenegativ daca x ≥ 0
  • Atentie! Trebuie sa alegeti un subsir al sirului, nu o subsecventa! Doar costul este calculat in functie de subsecvente
  • Va recomandam ca daca tineti in mana stanga dolarei, in mana dreapta sa aveti leii grei.

Exemplu

palsubsecv.inpalsubsecv.out
2
5 2 9
acbba
1 2 10
4 5 11
4 2 5
xyyx
3 4 2
2 3 3
2
4

Explicaţie

In primul exemplu, ori luam subsirul aa ori bb. Nu putem sa le luam pe ambele, deoarece ar trebui sa platim 11 dolarei din cauza ca luam toate caracterele din intervalul [4, 5].

In al doilea exemplu, luam intregul sir S si platim 2 + 3 = 5 dolarei.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?