Lista de probleme 54

Funcționarea computerelor cuantice se bazează pe organizarea internă a particulelor elementare din cadrul hiperprocesorului hadronic conform legilor mecanicii cuantice. Pentru a crește viteza de procesare a unui astfel de sistem de calcul, trebuie determinată o dispunere specială a hadronilor în cadrul câmpului de influență al forței nucleare puternice care să asigure integritatea plasmei quark-gluon.

Un canadian deține o firmă cu n muncitori. Fiecare din aceștia lucrează la m case, codificate prin numere naturale. Canadianul dorește să afle:

1) numărul maxim de muncitori care lucrează la aceeași casă;
2) numărul maxim de case la care lucreaza simultan cel putin doi muncitori.

Kida a descoperit un nou joc, prin care pornind de la un număr oarecare poate ajunge la alte numere prin niște pași simpli: dacă la un moment de timp, T, Kida are numărul W, atunci la momentul de timp T + 1 ea poate să ajungem la orice alt număr L dacă:

• L < W
• L este divizibil cu W - L
• W este divizibil cu W - L
• 2 * L ≥ W

Kida are o mulțime de N numere, notată cu D. Acum, ea își pune Q întrebări de tipul: Dacă aș porni la momentul de timp T = 0 și aș avea numărul x, care este momentul de timp minim la care aș putea sa ajung la un număr din mulțimea D folosind regulile jocului descris mai sus? Dacă nu se poate ajunge la niciun număr din mulțimea D, atunci Kida va considera că răspunsul este -1.

Vom considera un segment pe axa Ox care începe la poziția 0 și se termină la poziția L.
Se vor insera pe rând N puncte pe axă, iar după fiecare punct inserat se va afișa lungimea celui mai lung segment delimitat de două puncte (inclusiv 0 și L).

Jimmy se joacă cu un string S, inițial gol, pe care poate realiza următoarele operații:

• adaugă o literă mică oarecare ch la sfârșitul string-ului (1 ch)
• elimină ultimul caracter din string (2)
• afișează string-ul (3)

Jimmy deține și o mulțime de string-uri M și se întreabă care este numărul minim necesar de operații pe string-ul S pentru a afișa toate string-urile din mulțimea M, într-o ordine oarecare?

Chimmy are un șir de N numere întregi și Q întrebări de forma a b, unde pentru fiecare întrebare Chimmy dorește să afle, pe parcurgerea șirului de la poziția a la poziția b, de câte ori se schimbă maximul. Chimmy, neștiind să programeze, vă cere să îl ajutați pentru 100 de puncte!

Se dă un vector de N numere naturale. Se dau deasemenea Q query-uri de forma l r, unde se cere suma tuturor subsecvențelor de elemente consecutive. Mai formal, pentru fiecare query [l, r], se cere rezultatul funcției F(l, r) = \( \sum_{i=l}^{r} \sum_{j=i}^{r} \) S(i, j), unde S(l, r) este suma tuturor elementelor din secvența [l, r].

Se dau N progresii aritmetice. Pentru fiecare se cunoaşte valoarea primului element şi raţia. Se mai dă o valoare X.
Determinaţi numărul de şiruri strict crescătoare care au următoarele proprietăţi: primul termen are valoarea 0, ultimul termen are valoarea X, oricare doi termeni consecutivi sunt termeni consecutivi în cel puțin una dintre progresiile date.

Se dau n+1 numere naturale mai mici decât n, dintre care unul singur se poate repeta. Să se afișeze al k-lea numar din șir si termenul care se repeta.

La un parc de sporturi de iarnă au venit G grupuri de schiori numerotate de la 1 la G. Aceștia coboară pe
una dintre cele 2 pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.

Un T-bar poate trage maxim 2 schiori odată. Deoarece sunt 2 pârtii, se formează 2 rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că 2 schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se
urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).

Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?