Lista de probleme 9

TH este foarte pasionat de șiruri palindromuri. El are un șir de caractere ce conține litere ale alfabetului englezesc A, indexat de la 1 și își pune M întrebări de forma: “Pentru x și y, în câte moduri pot împărți șirul A[x...y] în secvențe palindrom? Acest număr poate fi foarte mare, așa că mă mulțumesc cu rezultatul modulo 666013”.

Fie un șir de n litere mici. Să se determine lungimea maximă a unui subșir care este palindrom.

Avem un vector de n elemente naturale nenule. O operație constă în alegerea unei subsecvențe (elemente adiacente) palindromice și eliminarea ei din vector, în urma eliminării elementele rămase se vor restrânge. Care este numărul minim de operații necesar pentru a elimina toate elementele?

Se consideră un șir de numere naturale a[1], a[2], …, a[n]. Asupra șirului efectuăm n operații. O operație constă din eliminarea unuia din numerele de la capetele șirului. Deci la primul pas se elimină fie a[1], fie a[n]. Dacă la pasul i se elimină elementul a[k], atunci costul eliminării este i * a[k]. Să se determine costul maxim posibil total al celor n operații.

Echipa spațială s-a deghizat în locuitorii unei planete înapoi, cunoscută sub numele de „Pământ”. În timpul șederii lor s-au interesat de muzica acestor așa-numiți oameni, în special a genului obscur cunoscut sub numele de “space jazz”. În loc să fie jucat la o scară obișnuită, se joacă pe space jazz, o scară de 26 de note, etichetate de la “a” la “z”. Un compozitor de space jazz scrie o piesă de space jazz așa cum urmează să fie descris. Începe cu o foaie goală de hârtie. Apoi alege o anumită notă de la “a” la “z” și scrie nota de două ori. Apoi alege în mod repetat o nouă notă (ar putea fi aceeași sau diferită de cea anterioară) și o scrie de două ori între două note adiacente sau lângă altă notă. De exemplu, un compozitor ar putea începe prin a scrie “gg”, apoi adaugă “oo” pentru a face “goog”, apoi adaugă “aa” pentru a face “aagoog” și așa mai departe. Problema este că toate spectacolele pe care le ascultă echipa spațială lasă afară note. Având în vedere notele jucate într-o reprezentație de space jazz, ajutați-i să-și dea seama numărul minim de note care au fost lăsate deoparte, având în vedere că original piesa a fost o compoziție valabilă de jazz spațial.

Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

În fața palatului Prințesei Mofturoase se află n pețitori așezați la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre prețioase pe care dorește să le ofere prințesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prințesa a decis să-i determine ca n-1 dintre ei să renunțe în chip pașnic, pețitorul rămas devenind alesul prințesei (indiferent de numărul de pietre prețioase deținute de acesta). Doi pețitori vecini la coadă se pot înțelege între ei astfel: cel care are mai puține pietre prețioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre față de câte avea. Dacă doi pețitori au același număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său. Un pețitor se poate înțelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui pețitor, toți cei din spatele lui avansează.

Fie P numărul de pietre prețioase pe care le are pețitorul care va deveni alesul prințesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.

Se dă un șir de caractere de lungime N format din litere mari ale alfabetului englez și un număr întreg K. Asupra șirului se poate aplica în mod repetat următoarea operație: se alege o subsecvență de lungime cel putin K având toate elementele egale și se elimină din șir. Evident că prima dată operația se aplică asupra șirului inițial și ulterior asupra șirului obținut din aplicarea operației anterioare. Operația se aplică până când șirul devine șirul vid (de lungime 0) sau șirul nu mai conține subsecvențe de lungime cel puțin K cu toate elemente egale.
Cunoscând N, K și șirul de caractere, să se determine care este lungimea minimă la care poate fi redus șirul după aplicarea operațiilor într-un mod convenabil.

George este un mare iubitor al informaticii, dar este încă la început și de aceea are nevoie de ajutorul vostru. La ora de informatică profesoara scrie pe tablă N numere naturale, iar la fiecare pas George trebuie sa aleagă două numere de pe poziții consecutive și să le înlocuiască cu un singur număr egal cu partea întreagă a mediei lor aritmetice. George trebuie să facă aceste înlocuiri până când mai rămâne pe tablă doar un număr. Ajutați-l pe George sa afle care este cel mai mare număr care poate fi obținut la final.