Lista de probleme 888

Oricare cuvânt care nu este de tip palindrom se poate separa în mai multe părți care, fiecare, să fie de tip palindrom. Care este numărul minim de secvențe de tip palindrom în care se poate separa un cuvânt și care este cea mai mare lungime a unei asemenea secvențe?

Dându-se un cuvânt format din litere mari și mici ale alfabetului englez și cifre, să se afle numărul minim de caractere care pot fi inserate în cuvânt pentru a deveni PALINDROM. Caracterele pot fi inserate oriunde în cuvânt.

Se dă un vector v cu N elemente numere naturale numerotate de la 1 la N și M întrebări de forma:

• x y p: se afișează valoarea ce s-ar afla pe poziția p dacă v[x...y] ar fi ordonat crescător.

Avem o matrice triunghiulară cu n linii, cu elemente numere întregi. În această matrice putem construi un traseu după următoarea regulă:

• primul element al traseului este elementul a1,1
• dacă elementul ai,j aparţine traseului, atunci următorul element al traseului poate fi doar ai+1,j sau a_i+1,j+1, pentru orice 1≤j≤i<n.
• traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la 1 la n. Valoarea traseului este egală cu suma elementelor ce îl formează.
  Traseul evidenţiat în exemplul din dreapta are valoarea 5+4+6+5+4=24, şi se codifică cu 1,2,3,3,4.

Fie mulţimea tuturor traseelor de valoare maximă generate în ordine lexicografică și numerotate. Pentru exemplul de mai sus avem șase trasee de lungime maximă:

• traseul 1. 1 1 1 1 2 (5+2+7+6+4=24)
• traseul 2. 1 1 1 2 2 (5+2+7+6+4=24)
• traseul 3. 1 2 2 2 2 (5+4+5+6+4=24)
• traseul 4. 1 2 3 3 4 (5+4+6+5+4=24)
• traseul 5. 1 2 3 4 4 (5+4+6+5+4=24)
• traseul 6. 1 2 3 4 5 (5+4+6+5+4=24)

Cunoscând dimensiunea și elementele unei matrice triunghiulare, respectiv două numere naturale st şi dr (st≤dr), se cere să se determine:

1. Numărul total al traseelor de valoare maximă. În cazul în care această valoare depășește 2000000000, se va tipări valoarea 2000000001;
2. Traseele cu numerele de ordine st, st+1, … , dr.

Se dă un graf orientat aciclic cu N noduri numerotate de la 1 la N. Să se realizeze o sortare topologică a nodurilor.

Rufus pleacă din punctul de linie 1 și coloană 1 al matricei, iar Rufia îl asteaptă în punctul de linie N și coloană M. Fiind un teren accidentat, acesta consumă o anumită energie și un anumit timp pentru a ajunge dintr-un punct în unul din cele maxim 8 puncte vecine ale sale, cu condiția să rămână în interiorul spațiului bine delimitat.
Energia consumată pentru a ajunge în punctul de linie i și coloană j din unul din punctele sale vecine este dată de valoarea lui | A[i][j] | (valoarea lui A[i][j] în modul ), iar timpul consumat pentru a ajunge în acest punct dintr-un punct vecin este dat de valoarea T[i][j].

Ajutați-l pe Rufus să ajungă la prietena sa Rufia în cel mai scurt timp posibil și găsiți, de asemenea, capacitatea fizică inițială minimă, știind că aceasta poate fi cel mult K.

Se consideră o colecție de numere naturale, inițial vidă. Asupra ei se fac două tipuri de operații:

• 1 x – valoarea x se adaugă în colecție;
• 2 – cea mai mare valoare din colecție se afișează, apoi se elimină din colecție.

Dându-se un șir de m operații, să se afișeze în ordine rezultatele operațiilor de tip 2.

Se dau n numere naturale, reprezentând în ordine valorile nodurilor dintr-un arbore binar complet și m operații de tip 1 sau 2, aplicate unui nod k.

Operația de tip 1 determină valoarea nodului părinte a lui k, iar operația de tip 2 determină suma valorilor fiilor nodului k. Dacă k=1 sau dacă nodul k nu are fii, rezultatul va fi 0.

Afișați pentru fiecare operație rezultatul ei.

Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.

Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la N. Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.

La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.

Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:

• La dreapta, ajungând în sectorul (i,j+1) .
• Pe diagonala la dreapta în sus, ajungând în sectorul (i-1,j+1).
• Pe diagonala la dreapta în jos, ajungând în sectorul (i+1,j+1).

Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.

Se dă un număr natural s. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe s ca produs de divizori proprii distincți ai lui s.