Lista de probleme 749

Se consideră n copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la 1 la n. Pentru fiecare copac se cunoaşte înălţimea sa \( {H}_{i} \). Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac i se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac i considerăm un şir \( {d}_{1}, {d}_{2}, …, {d}_{x} \) reprezentând prietenii copacului i situaţi în dreapta sa şi un şir \( {s}_{1}, {s}_{2}, …, {s}_{y} \) reprezentând prietenii copacului i situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac i formează împreună lista prietenilor acestuia. Şirurile corespunzătoare copacului i se definesc astfel:

1. \( {d}_{1} = i + 1 \) (dacă i = n, atunci copacul i nu are niciun prieten la dreapta sa, şirul rămânând vid). Pentru fiecare k ≥ 2, \( {d}_{k} \) este cel mai mic indice (\( 1 ≤ {d}_{k} ≤ n \)) cu proprietatea că \( {d}_{k} > {d}_{k-1} \) şi \( {H}_{{d}_{k}} > {H}_{{d}_{k-1}} \). Dacă \( {d}_{k} \) nu există, atunci lista de prieteni la dreapta ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.
2. \( {s}_{1} = i – 1 \) (dacă i = 1, atunci copacul i nu are niciun prieten la stânga sa, şirul rămânând vid). Pentru fiecare k ≥ 2, \( {s}_{k} \) este cel mai mare indice (\( 1 ≤ {s}_{k} ≤ n \)) cu proprietatea că \( {s}_{k} < {s}_{k-1} \) şi \( {H}_{{s}_{k}} > {H}_{{s}_{k-1}} \). Dacă \( {s}_{k} \) nu există, atunci lista de prieteni la stânga ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.

Determinaţi în câte moduri se pot alege 3 copaci diferiţi dintre cei n cu proprietatea că, oricum am alege 2 copaci dintre cei 3, fie aceştia copacul A şi copacul B, atunci A este prieten cu B şi B este prieten cu A.

Să se cripteze sau să se decripteze un mesaj folosind cifrul Playfair.

Se consideră o expresie corectă formată din numere naturale, paranteze rotunde și operatorii +, -, *. Să se evalueze expresia.

RAU-Gigel se gândește la un joc cu piesele de șah. El desenează o tablă de șah sub forma unei matrici pătratice de latură N și așează în fiecare dintre cele N x N celule câte o piesă de șah. Se consideră că dispune de N X N exemplare din fiecare piesă posibilă (regi, regine, ture, nebuni, cai, pioni), iar culoarea nu este relevantă. RAU-Gigel se întreabă care este numărul minim de căsuțe (celule) prin care trebuie să treacă un rege oarecare ca să ajungă la o regină oarecare. Regele se poate deplasa câte o celulă în patru direcții posibile: N, E, S, V.

Dar asta nu e tot. La începutul jocului, toți regii au 16 vieți. Atunci când RAU-Gigel mută un rege (oarecare) peste primul pion, acesta pierde o viață. Vestea bună este că, după aceea, regele respectiv poate lua oricâți pioni fără ca numărul său de vieți să fie afectat. Când ia un cal, regele pierde două vieți, dar după aceea poate lua, fără pierderi, oricâți cai. La fel se întâmplă și în cazul nebunilor, primul nebun îl costa patru vieți și, respectiv al turelor, care îl costă opt vieți.

RAU-Gigel dorește să afle ce rege să aleagă și pe ce traseu trebuie să meargă acesta către o regină oarecare, astfel încât la sfârșitul jocului să îi rămână cât mai multe vieți, iar traseul să fie cât mai scurt.

Se dă un string s. Asupra acestuia, se aplică 5 tipuri de operații:

• (1, c) – se adaugă caracterul c la începutul string-ului
• (2, c) – se adaugă caracterul c la finalul string-ului
• (3) – se șterge primul caracter al string-ului
• (4) – se șterge ultimul caracter al string-ului
• (5) – string-ul se va transforma în răsturnatul său

Să se afișeze string-ul rezultat după cele q operații.

Se consideră o expresie aritmetică formată din numere naturale și operatorii binari + (adunare), - (scădere), * (înmulțire), ^ (ridicare la putere). Să se determine forma postfixată corespunzătoare și să se calculeze valoarea expresiei.

Să se scrie o funcție care să elimine nodurile care conțin duplicate dintr-o listă care are valorile ordonate crescător.

Codificati un mesaj folosind cifrul Four Square.

Se dă un șir s de caractere (litere mici ale alfabetului englez), urmat de un număr natural k. Să se afișeze câte subsecvențe ale șirului s de lungime 1, 2, … k sunt palindromuri.

Respectând normele de distanțare socială, cei \( \frac{k\cdot (k+1)}{2} \) cetățeni din comuna lui Dorel s-au programat la magazinul din localitate pentru a face cumpărăturile de Paște, în k zile: în prima zi k cetățeni, în a doua zi k-1 dintre cei rămași, ș.a.m.d., în ultima zi ultimul cetățean.

Fiind date t valori ale lui k, numere naturale, aflați pentru fiecare în câte moduri poate fi făcută planificarea pe zile pentru cumpărăturile de Paște.