Lista de probleme 974

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.

Cei N copii de la școala generală vor să formeze o echipă de fotbal compusă din K elevi, dintre care cel puțin unul stângaci și cel puțin unul dreptaci. Pentru fiecare copil i (de la 0 la N-1) se cunoaște intervalul de timp în care acesta este disponibil pentru a face parte din echipă, sub forma unei perechi, [starti, endi], cât și dacă este stângaci sau dreptaci. K copii pot juca în aceeași echipa dacă intervalele de timp în care aceștia sunt disponibili se suprapun în cel puțin un punct (moment de timp). Se cere numărul de moduri în care se poate alcătui o echipă cu K dintre cei N elevi; deoarece acest număr poate să fie foarte mare, el se va afișa modulo 1.000.000.009.

Construcția unei noi clădiri a fost finalizată! Frank, celebrul arhitect a făcut o poză cu fațada. Nu este chiar mulțumit de poză deoarece a observat o înclinație a pozei relativ la orizontală. Asta se poate repara printr-o rotație, iar Frank se întreabă dacă procesul de îndreptare nu ar putea fi automatizat. Cu acest scop, imaginea este transformată într-o mulțime de segmente din plan, detectate automat cu algoritmi speciali, ca în imaginea din dreapta. Segmentele care se obțin sunt identificate prin cele două extremități, puncte având coordonate numere naturale, în sistemul xOy: (x1, y1), (x2, y2). Un segment este numit aliniat cu axele dacă este orizontal paralel cu axa Ox, deci y1 = y2) sau vertical (paralel cu axa Oy, deci x1 = x2). Prin rotația imaginii în ansamblu, o parte dintre segmente devin aliniate cu cele două axe. Scrieți un program care pentru o mulțime de segmente determină numărul maxim de segmente care se pot alinia prin rotirea cu un același unghi a tuturor segmentelor. Unghiul de rotație poate fi orice număr real.

Fie S un șir de caractere de lungime N indexat de la 1. Pe un astfel de șir se definește operația swap: se alege un indice i (1 ≤ i < N) și se interschimbă caracterele S[i] și S[i + 1]. Numărul norocos corespunzător unui șir S este egal cu numărul minim de operații swap ce trebuie efectuate succesiv pentru a obține cel puțin o subsecvență bingo în șirul S. Dacă subsecvența bingo apare în șirul inițial, numărul norocos este egal cu 0. Se dă un număr natural T și T șiruri de caractere. Să se determine pentru fiecare șir dat S[i] (1 ≤ i ≤ T), numărul său norocos.

Cunoscându-se N și M, dimensiunile satului, C numărul cailor, forțele inițiale ale cailor și matricile a și p, să se determine numărul de cai pe care Lică îi poate utiliza astfel încât el să reușească să traverseze satul, de la casa lui până la ieșirea din sat.

Dându-se un șir A de N numere naturale nenule numerotate de la 1 la N, să se determine câte subsecvențe [L,R] cu 1 < L ≤ R < N există, astfel încât elementele A[L], A[L+1],…, A[R] să fie strict mai mari decât elementele A[L-1] și A[R+1]. De asemenea, se cere și determinarea lungimii maxime a unei astfel de secvențe. Scrieți un program care să rezolve următoarele două cerințe:
1) Să se determine lungimea maximă a unei subsecvențe ce respectă proprietatea din enunț;
2) Să se determine numărul de subsecvențe ce respectă proprietatea din enunț.

Satul Binăreni se află în pericol în urma incendiilor provocate în ultima lună. Acesta este reprezentat printr-o matrice binară cu N linii și M coloane. Toate celulele care au luat foc sunt reprezentate prin valoarea 0. Toate celulele în care nu este produs un incendiu, reprezentate prin valori de 1, conțin, inițial, câte o casă a unui sătean. Gosu, cel mai renumit pompier din sat, își dorește să salveze toate casele care nu se află în celule "safe", folosindu-și superputerea: acesta poate stinge o singură dată focul din toate celulele care au luat foc pe o linie x și toate celulele care au luat foc pe o coloană y, plasându-se la intersecția acestora, în celula (x, y). Acesta se poate plasa atât pe o celulă cu incendiu, cât și pe o celulă care conține o casă. Având în vedere că Gosu își poate folosi superputerea o singură dată, aflați toate perechile de coordonate (x, y) posibile pe care se poate plasa acesta, astfel încât să salveze toate casele care sunt în pericol.

Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 1. Trebuie să răspundeți la Q query-uri de forma x, y – calculați câte inversiuni se află în intervalul [x, y]. O inversiune este o pereche de indici (i, j), 1 ≤ i < j ≤ N, pentru care este adevărată relația Si > Sj.

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

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}…{s}_{l-1}] \), \( [{s}_{j}{s}_{j+1}…{s}_{j+l-1}] \) și \( [{s}_{i-l+1}{s}_{i-l+2}…{s}_{i}] \) sunt egale. Dacă nu există un astfel de l, afișați valoarea 0.