Lista de probleme 6

Să considerăm o tablă de șah de dimensiune n (n este par), în care liniile și coloanele sale sunt numerotate de la 1 la n. Pe această tablă se află, pe fiecare pătrat, câte un număr natural astfel încât suma numerelor de pe pătratele albe este egală cu suma numerelor de pe pătratele negre. Definim două operații:

• 1 i j k p x – adună la valorile două pătrate vecine aflate pe pozițiile (i,j) și (k,p) același număr natural x.
• 2 i j k p – scade din valorile două pătrate vecine aflate pe pozițiile (i,j) și (k,p) valoarea minimă reținută pe cele două poziții.

Utilizând un număr cât mai mic de operații de tip 1 sau 2 să se obțină pe tabla de șah numai valori nule.

La o tragere loto expres specială se extrag M numere distincte din mulţimea {1, 2, 3, ..., 49}. O persoană care joacă la acest joc scrie pe bilet K numere distincte dintre cele 49 posibile. La tragere au cumpărat bilete J jucători. Un jucător câștigă la cea mai valoroasă categorie la care se încadrează. Să se scrie un program care să determine:

• Numărul de jucători câștigători pentru o categorie specificată C de câștig. Categoriile sunt numerotate {1, 2, ..., 6, 7}. Categoria 7 este destinată necâștigătorilor.
• Numerele care sunt alese de numărul maxim de jucători, scrise în ordine crescătoare.

Expresia este o succesiune formată din unul sau mai mulți operanzi. În expresie apar doar doi operatori, a căror semnificaţie spionul o ştia deja:

• + – concatenează două șiruri (ex: con + tact = contact)
• * – inserează al doilea şir după fiecare literă a primului şir (ex: Ctrm * a = Catarama)

Operaţiile din expresie se execută în ordine, de la stânga la dreapta. Valoarea este un şir de caractere care reprezintă rezultatul evaluării expresiei. Scrieţi un program care, cunoscând indiciul, determină codul.

Date fiind numărul N de parcele, K – numărul maxim de parcele pe care le poate parcurge planorul ce pornește de la înălțime zero, precum și diferențele de nivel corespunzătoare fiecăreia dintre cele N parcele să se rezolve următoarele 3 cerințe:
1) înălțimea maximă la care ajunge planorul dacă pleacă din prima parcelă și parcurge cel mult K parcele (dar cel puțin una);
2) înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă X de lansare și după ce parcurge exact K parcele;
3) înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă X de lansare și parcurge cel mult K parcele (dar cel puțin una).

Se dă un graf conex neorientat G cu N noduri și M muchii, fiecare muchie având asociat un cost. Un arbore parțial pentru G este un subgraf cu structura de arbore, care cuprinde toate nodurile și o parte din muchii. Se cere găsirea unui arbore parțial al grafului G, astfel încât diferența dintre cel mai mare și cel mai mic cost al unei muchii să fie minimă.

De ziua lui, Florin a primit un șir de caractere periodic și infinit. Perioada lui are lungime n și conține doar litere mici ale alfabetului englez. Deoarece este curios, el vrea să își personalizeze șirul primit în diverse moduri. Pentru a face asta, el vă dă q operații care se realizează pe șirul dat, operații de două tipuri, după cum urmează:

• 1 x y: Litera de pe poziția x devine egală cu y, unde y este o literă mică a alfabetului englez.
• 2 a b c: Florin vrea să afle câte litere egale cu c există între pozițiile [a, b] din șirul de caractere.

Fiindcă nu vrea să strice periodicitatea șirului foarte mult, Florin vă garantează că pentru toate operațiile de actualizare, valorile pozițiilor modificate au în reprezentarea binară cel mult k biți egali cu 1. Scrieţi un program care, dându-se șirul de caractere și actualizările, răspunde la interogări.