Lista de probleme 14

Se dă un limbaj format din N cuvinte și un text criptat format din M cuvinte. Spunem că un cuvânt se permută după un șir \({x}_{1}, {x}_{2}, …, {x}_{K} \) dacă prima literă se permută cu \({x}_{1}\), a doua cu \({x}_{2}\), …, iar ultima cu \({x}_{K}\).
De exemplu, după șirul 1 5 6, “abc” devine “bgi”. Permutarea se face în ordinea literelor mici din alfabetul englez. Dacă o literă ar trece de finalul alfabetului, aceasta îl reia și apoi permută și litera următoare cu 1.
În cazul în care ultima literă trece de finalul alfabetului, atunci cuvântul devine invalid. De exemplu, “zza” permutat după șirul 1 2 3, devine “ace”. (adunarea se face cu transport pornind de la stânga). Dacă “zzz” s-ar permuta după șirul 1 2 3, ar deveni invalid. Cele mai “semnificative” litere sunt de la dreapta la stânga.
Vrem să decriptăm textul, folosind mai multe variante de șiruri pe care le considerăm valabile. Cel mai bun șir de decriptare este acela pentru care numărul de cuvinte din textul criptat care se găsesc, după operație, în limbaj, este maximal.

În grădina lui Cosmin se află un măr cu număr nelimitat de mere. Cei N prieteni ai lui Cosmin, numerotați de la 1 la N, vor culege mere timp de T zile, după următoarea regulă:
În dimineața zilei Ti, prietenii lui Cosmin vor forma o coadă la intrarea în grădina, începând cu prietenul Xi. Așadar, coada va arăta sub forma Xi, Xi+1, …, XN, X1, …, Xi-1. În acea zi se vor culege Yi mere. Fiecare prieten Xi va intra în grădină, va culege un măr și se va întoarce în coadă.
În ziua T + 1, Cosmin alege aleatoriu K prieteni (Q1, …, Qk) și dorește să afle câte mere a cules fiecare. Scrieţi un program care să găsească numărul de mere culese de fiecare dintre cei K prieteni selectați de Cosmin.

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr x, iar altul un număr y mai mare sau egal cu x. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la x și y. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea. Să se calculeze pentru fiecare întrebare p minimum, pentru care relația este satisfăcută.

Se dă o instalație de N * M lumini. Fiecare lumină este dată prin culoare, în format RGB. Astfel, un element din matrice poate fi considerat un triplet (xR , xG , xB). Fiecare valoare este de la 0 la 255.
1) Câte perechi există în matrice, pentru care conexiunea lor ar determina culoarea negru?
2) Pentru o astfel de instalație dată, care este numărul maxim P, pentru care instalația nu se blochează?

Mihăiță s-a hotărât să își construiască un gard perfect cu ajutorul lui Dorel – un constructor renumit.
Un gard perfect trebuie să respecte următoarele cerințe:
1. Gardul să fie format din N scânduri de înălțimi nu neapărat egale;
2. Scândurile pot fi așezate în orice ordine;
3. Există un număr egal de scânduri pentru fiecare înălțime;
Mihăiță acceptă un gard ca fiind perfect dacă respectă condițiile de mai sus înainte sau după eliminarea unei singure scânduri. Ajutați-l pe Mihăiță să verifice perfecțiunea celor T garduri propuse de Dorel.

În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe. Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața sa. Fiind dat șirul inițial de observații ale oamenilor care stau la coadă, să se reconstruiască șirul minim lexicografic care poate reprezenta înălțimile acestora.

În jurul muzeului din orașul Smallville exista un gard ce conține N scânduri de înălțimi diferite. Putem spune că scândura i are înălțimea Hi. Directorul muzeului le-a cerut angajaților să vopsească acest gard cu un număr minim de culori, astfel încât să se respecte următoarea condiție: pentru un număr întreg K cunoscut, orice secvență de K scânduri consecutive nu trebuie să conțină două scânduri de aceeași înălțime, colorate identic. Scrieţi un program care să găsească numărul minim de culori ce vor fi folosite pentru a colora gardul.

Pentru că este un bun sportiv și poate alerga constant cu x metri pe secundă, Gigel și-a propus să câștige competiția semarun. Această competiție începe la momentul 0 și constă în parcurgerea unui traseu de n metri, ce conține k semafoare. Deoarece Gigel știe că nu este important să ajungă primul la final, ci să parcurgă traseul într-un timp cat mai scurt, vă roagă să îl ajutați cu următoarea cerință: determinați momentele de timp pe care Gigel ar putea sa le aleagă pentru a începe parcurgerea traseului astfel încât să nu se oprească la niciun semafor și atunci când ajunge la final să nu fi trecut mai mult de s secunde de la începutul competiției (momentul 0).

Alex și Mircea, membri veterani ai Comisiei de Entertainment la concursurile de informatică, au fost chemați de către comisia științifică să participe la ediția de anul acesta a concursului InfoOltenia. Comisia științifică le-a spus acestora locația secretă în care se află și le-a transmis că îi așteaptă cu nerăbdare. Cum Alex și Mircea nu pot spune pas la o asemenea ocazie, se pregătesc imediat de plecare. Aceștia, fiind pasionați și de informatică în timpul liber, își pun următoarea întrebare: în câte moduri pot ajunge de la ei de acasă până la locația comisiei științifice?

Formal, harta județului Vâlcea poate fi interpretată ca un grid, în care veteranii se află la coordonatele (0,0), iar comisia se află la coordonatele (m,n). Cum veteranii nu se deplasează decât înainte, dintr-o celulă de coordonate (i,j), aceștia pot face următorul pas într-una din celulele aflate la coordonate (i+1,j), (i,j+1) sau (i+1,j+1). Să se calculeze numărul de moduri în care Alex și Mircea pot ajunge la locația comisiei științifice. Cum numărul acesta poate fi foarte mare, se vrea furnizată valoarea acestuia modulo 666013.

Se dă o listă, inițial vidă, cu numere. Toor dorește să completeze lista asta, adăugând numere pe care le consideră importante pentru cmmdc. La fiecare moment, dorește să afle cmmdc-ul tuturor numerelor care sunt în listă atunci. Câteodată, scoate un număr care este în listă, pentru a putea adăuga ulterior altele. Prin convenție, cmmdc-ul unei mulțimi cu 0 elemente este 1. Să se determine după fiecare operație cmmdc-ul mulțimii actuale de numere.