Lista de probleme 240

Se dă un șir de caractere s, care poate conține doar litere mici și mari ale alfabetului englez (de la a la z și de la A la Z). Pentru toate perechile neordonate de subsecvențe distincte ale șirului s care au lungimi egale, vrem să calculăm distanța dintre ele și să afișăm suma acestora modulo 1.000.000.007. Formal, se cere suma valorilor dist(s(a, b), s(c, d)), pentru toți indicii a, b, c, d cu 0 ≤ a, b, c, d < |s|, a < c, a ≤ b, c ≤ d, b - a = d - c, modulo 1.000.000.007. |s| reprezintă lungimea șirului s, care este indexat de la 0.

Un laborator specializat studiază mutațiile unui virus pandemic pentru a găsi cel mai bun vaccin pentru combaterea acestuia. Codul unui virus este un șir format din litere (mari și mici) ale alfabetului englez. Numim mutație a virusului pandemic un șir de caractere care are aceeași lungime cu codul virusului și care conține o singură poziție pentru care litera din șir este diferită de litera situată pe poziția respectivă în codul virusului pandemic. Scrieți un program care, cunoscând codul virusului pandemic și lista codurilor virușilor descoperiți în urma testărilor, rezolvă următoarele cerințe:

1. Determină numărul de mutații ale virusului pandemic existente în listă, mutații nu neapărat distincte;
2. Determină mutația cu număr maxim de apariții în listă; dacă există mai multe mutații cu același număr maxim de apariții, se va determina prima mutație, în ordine lexicografică.

Se dă un șir S format din litere mici ale alfabetului englez. O secvență din şir este palindromică dacă prin parcurgerea sa de la dreapta la stânga se obține același cuvânt precum la parcurgerea de la stânga la dreapta. Se formulează m întrebări de forma i, j, k cu semnificația: pornind de la secvența formată din caracterele dintre indicii i și j inclusiv și având posibilitatea să o extindem în total cu maximum k caractere în S (imediat în stânga poziției i și/sau imediat în dreapta poziției j), putem să obținem o secvență palindromică?

Se consideră N șiruri de caractere, fiecare șir având lungimea N. Șirurile conțin caractere din mulțimea {a, b, ..., z, #}. Putem privi cele N șiruri ca o matrice pătratică de N x N caractere. Să se determine numărul total al romburilor corect formate precum și latura celui mai mare romb care se poate construi în matrice astfel încât acesta să aibă în cele patru colțuri caracterul #, fiecare latură a perimetrului rombului să conțină cel puțin o vocală, iar restul caracterelor care alcătuiesc rombul să fie diferite de caracterul #.

O imprimantă circulară are litere mari ale alfabetului englezesc dispuse circular de la A la Z. Imprimanta are un indicator care inițial este plasat la litera A. Imprimanta tipărește literele în două culori roșu sau albastru. Unele litere se tipăresc cu cerneală roșie, restul cu cerneală albastră. Pentru simplitate le vom numi litere roșii și litere albastre. Fiind date un șir de litere albastre nu neapărat distincte și mulțimea literelor roșii ale imprimantei, să se calculeze:

• Care este timpul pentru tipărirea la imprimantă circulară a șirului de litere albastre.
• Să se insereze între oricare două litere albastre aflate pe poziții consecutive câte o literă roșie astfel încât să se obțină timpul minim pentru tipărire și să se afișeze: timpul minim, numărul de șiruri distincte care sunt tipărite cu timp minim, șirul minim lexicografic dintre toate șirurile ce sunt tipărite în acest timp

Alexandra citește un text format din litere mici și mari ale alfabetului englez și spații. Fiind interesată de criptografie, ea elimină toate spațiile și apoi încadrează literele, în ordinea în care acestea apar în text, într-un tablou bidimensional, în care numărul de linii este mai mic sau egal decât numărul de coloane. Întrucât pot exista mai multe moduri de încadrare a textului, Alexandra îl alege pe cel pentru care diferența absolută dintre numărul liniilor și al coloanelor tabloului este minimă.
1) Notând cu N numărul de linii și cu M numărul de coloane ale tabloul bidimensional obținut, afișați elementele acestuia pe primele N linii ale fișierului de ieșire, fiecare linie conținând exact M litere fără spații între ele. Afișarea se va face în ordinea crescătoare a indicilor liniilor și pe fiecare linie în ordinea crescătoare a indicilor coloanelor.
2) Determinați cel mai lung palindrom de pe o linie sau de pe o coloană a tabloului obținut. În cazul în care există mai multe palindromuri de aceeași lungime, se va afișa cel care este cel mai mare din punct de vedere lexicografic conform codului ASCII.
3) Determinați care este numărul maxim de elemente dintr-un subtablou dreptunghiular, ce conține doar vocale.

Ruz deține un parc de autoturisme. În parcul său toate mașinile sunt stocate într-o bază de date din propriul calculator și sunt identificate după trei elemente m, nr și p, unde m reprezintă marca autoturismului, nr reprezintă numărul de înmatriculare al autoturimului, iar p reprezintă prețul de vânzare. El dorește să dezvolte o aplicație pentru a afla în orice moment care este numărul de mașini înmatriculate în județul Iași, marca mașinii care are prețul maxim, respectiv care este valoarea parcului de autoturisme. Scrieţi un program care să determine:
1) numărul de mașini din județul Iași, având codul IS.
2) marca mașinii cu prețul maxim.
3) valoarea parcului de autoturisme.

Gigel trebuie să verifice dacă fratele mai mic are tema rezolvată corect. Dorința lui este să scape cât mai repede de această sarcină obositoare, de aceea vă roagă să îl ajutați să calculeze adunările (+) și scăderile (-) pe care fratele lui le are ca temă. Din fericire pentru Gigel, fratele lui știe doar operații cu numere întregi. Scrieţi un program care să determine:
1. care este rezultatul unei expresii matematice e date.
2. valoarea maximă pe care o poate avea expresia e dacă putem schimba exact un singur operator din expresie.

Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 0. Aflați pentru fiecare i ≥ 2 cel mai mare l pentru care există 0 < j < i − l + 1 unde stringurile $[s_0{s}_1\dots s_{l-1}]$, $[s_j{s}_{j+1}\dots s_{j+l-1}]$ și $[s_{i-l+1}{s}_{i-l+2}\dots s_i]$ sunt egale. Dacă nu există un astfel de l, afișați valoarea 0.

Să considerăm un calculator cuantic cu N qubiți setați inițial la |q1⟩|q2⟩..|qN⟩. Asupra acestor qubiți se poate efectua un singur tip de operații: se inversează toți qubiții (|0⟩ devine |1⟩ și viceversa) dintr-o subsecvență (qubiți aflați pe poziții consecutive). Aflați numărul minim de operații necesare pentru a seta toți qubiții la |1⟩ în situațiile:
1. Operațiile se pot efectua asupra subsecvențelor de orice lungime
2. Operațiile se pot efectua doar asupra subsecvențelor de lungime K