Lista de probleme 898

Se dă un șir a1, a2, …, an de numere întregi. În acest șir, o secvență de cel puțin două elemente ai, ai+1, …, aj este validă dacă ai este strict mai mic decât aj. Cu alte cuvinte, secvența de cel puțin două elemente trebuie să aibă capătul din stânga strict mai mic decât capătul din dreapta al secvenței. Să se determine câte secvențe valide sunt în șir.

RAU-Gigel și Vlad sunt prieteni buni și le place tot timpul să se provoace unul pe altul. De data aceasta, RAU-Gigel a inventat o problemă interesantă de matematică.

Acesta are un arbore secret cu N noduri (numerotate de la 1 la N), în care fiecare nod are asociată o valoare (pe lângă numărul său de ordine din arbore), care este un număr natural și ii spune lui Vlad informații despre unele drumuri din acest arbore. O informație are forma x, y, val și reprezintă faptul că lanțul din arbore de la nodul x la nodul y are cel mai mare divizor comun al valorilor asociate nodurilor acestuia egal cu val, unde val este un număr natural nenul.

Vlad știe că RAU-Gigel minte câteodată și s-ar putea ca unele dintre restricțiile date să fie eronate, astfel că vrea să afle întâi folosind informațiile ce le are la îndemână dacă ar putea exista un arbore care să respecte toate restricțiile date de prietenul său.

Pentru că știe ce programator iscusit ești, Vlad ți-ar fi foarte recunoscător daca l-ai putea ajuta cu această problemă prin a scrie un program care să o rezolve cât mai eficient.

Fiind în vacanță, RAU-Gigel petrece mult timp jucându-se pe telefon. El are un joc cu cuvinte, de tip Scrabble, în care piesele sunt inscripționate cu litere (mici sau mari, ale alfabetului englez), fiecare literă din alfabet având o valoare cunoscută, număr natural. Valoarea unui cuvânt este egală cu suma valorilor literelor din cuvânt, fără a se ține cont de frecvența lor.

Prin unirea a două cuvinte se obține cel mai mic (alfanumeric) cuvânt format din toate literele prezente în cele două cuvinte, fără să ținem cont de tipul literei (mică/mare) sau de numărul de apariții. Notăm acest cuvânt cu a*b.

Costul unirii dintre două cuvinte este obținut prin însumarea valorilor literelor prezente în a*b, dar care nu sunt în a, respectiv, care nu sunt în b, ignorând tipul lor.

Aplicația lui RAU-Gigel generează un șir liniar cu N cuvinte, iar RAU-Gigel trebuie să unească două câte două cuvinte alăturate din șir, oricare, plătește costul necesar unirii lor, apoi înlocuiește în șir cele două cuvinte cu cuvântul obținut prin unire. La final, din șirul dat va rămâne un singur cuvânt, iar, pentru obținerea lui, RAU-Gigel va plăti suma tuturor costurilor generate pe parcurs.

Cerința este, ca, pentru un șir de N cuvinte, să se afle cuvântul final și costul total minim necesar obținerii acestuia.

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.

Dându-se o expresie aritmetică prefixată, postfixată sau infixată, să se afișeze toate celelalte forme ale ei.

Se dau numerele naturale nenule \(N\) și \(K\). Să se afle numărul așteptat de numere “nice” într-un șir generat aleatoriu care conține \(N\) numere de cel mult \(K\) cifre, modulo \( 1 \ 000 \ 000 \ 007 \).

Comisarul Roman se află în fața unui dispozitiv exploziv constând dintr-o piramidă cu N nivele numerotate de la 1 la N. Fiecare nivel i conține i bombe numerotate de la 1 la i. Notăm bomba j de pe nivelul i cu B[i, j]. Pentru fiecare bombă B[i, j] se cunoaște timpul în secunde T[i, j] de la momentul inițial după care aceasta explodează. Dispozitivul se consideră dezamorsat odată ce toate bombele au fost dezamorsate. Roman nu vrea să se grăbească, așa că ar vrea să știe care este numărul maxim de secunde X astfel încât, dacă ar începe operațiunea de dezamorsare cu o întârziere inițială de X secunde, dispozitivul ar putea fi încă dezamorsat cu succes. Pentru Q teste, date fiind N și valorile T[i, j] pentru 1 ≤ j ≤ i ≤ N, se cere numărul X.

Fascinată de cultura chineză și Marele Zid Chinezesc, Andra s-a hotărât să își construiască propriul zid în miniatură, de înălțime N și lățime M, din piese roșii și galbene pe care le deține. Ea are la dispoziție un număr nelimitat de piese cu lățimea de o unitate și toate înălțimile posibile. Piesele roșii (hóng) au înălțimea impară (1, 3, 5, ...), pe când piesele galbene (huáng) au înălțimea pară (2, 4, 6, ...). Piesele nu pot fi rotite și pot fi plasate doar pe verticală. Deoarece culoarea galbenă este considerată cea mai prestigioasă în cultura chineză, Andra vrea ca suma lungimilor tuturor pieselor galbene ce alcătuiesc zidul să fie egală cu un număr K, special ales astfel încât să aducă noroc. Mai mult de atât, ea se întreabă în câte moduri poate construi zidul astfel încât această condiție să fie respectată. Date fiind N, M și K, determinați numărul de moduri de a construi zidul în condițiile date.

Se dau două șiruri, A și B, cu valori din mulțimea {0, 1}.
1. Să se afle numărul de subsecvențe distincte din B care sunt subșiruri în A.
2. Să se afle, pentru o subsecvență B[p...q], numărul de subșiruri din A egale cu aceasta.
3. Să se afle numărul de subșiruri din A care sunt subsecvențe în B.

Andra are un pachet cu n tipuri de buline de ciocolată, cu câte c[i] buline de fiecare tip i. Andra dorește să utilizeze toate bulinele pentru a construi piramide, fiecare fiind formată din unul sau mai multe rânduri, numerotate începând de la 1. Pentru fiecare piramidă în parte, pe rândul i, se află 2i-1 buline. Spre exemplu, pe rândul 8 al unei piramide, se află 27 = 128 de buline de ciocolată. Pe fiecare rând al unei piramide se află unul sau mai multe tipuri de buline, iar același tip de buline se poate folosi pe oricâte rânduri. Dintre piramidele care se pot forma, cele serioase conțin pe fiecare rând doar un tip de buline. Folosind toate bulinele, ajutați-o pe Andra să determine:

1) Numărul minim de piramide de ciocolată pe care le poate forma.
2) Numărul minim de piramide serioase de ciocolată pe care le poate forma, astfel încât toate cele obținute să fie de acest fel.