Lista de probleme 58

Deși Trixie este considerată un membru vital al echipei, care își scoate deseori prietenii din bucluc, prințesa poate să fie și neîndemânatică. Transportarea robotului de la baza turnului până în laborator și invers mereu a fost o provocare pentru echipa. Trixie se grăbește să aducă robotul din laborator până la baza turnului. A fost nevoie de un singur pas greșit ca robotul să își inceapă coborârea pe cont propriu. Trixie observă că acesta se lovește de fiecare dintre cele n trepte, de fiecare dată lasând, în urma impactului, un număr de șuruburi. Numărul de șuruburi urmează o regulă fixă. Prima dată lasă în urmă un șurub, apoi tot un șurub, apoi 2 șuruburi, apoi 3 șuruburi, apoi 5 șuruburi, apoi 8 șuruburi ș.a.m.d. Practic numărul de șuruburi de pe treapta(i) = numărul de șuruburi de pe treapta (i - 1) + numărul de șuruburi de pe treapta (i - 2), pentru un i ≥ 3. Se vor da 3 numere naturale : n, m și ct. În funcție de ct, Trixie va avea una din 2 cerințe:

• Pentru ct = 1, să se determine produsul numerelor prime distincte, luate o singură dată, care apar în descompunerea în factori primi a numerelor de șuruburi, de pe trepte separate, mai mici decât 10 * m.
• Pentru ct = 2, să se determine restul împărțirii(%) numărului de șuruburi de pe treapta n la m.

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.

Cu ocazia intrării în sezonul 8 al competiției de robotică FTC, Trixie se decide să își ajute echipa și să curețe terenul pe care au loc sesiunile de antrenament ale echipei. Tema sezonului acesta implică un teren de dimensiuni nemaivăzute până acum, care poate fi reprezentat sub forma de matrice cu n linii și m coloane, matrice cu n * m tile-uri (bucăți de teren cu o formă asemănătoare unei piese de puzzle) pe care Trixie scrie n * m numere naturale notate t[i][j], câte unul pentru fiecare tile. De asemenea, este important să menționăm că terenul este prevăzut cu pereți laterali pe toate cele 4 laturi, astfel încât Trixie nu poate ieși din perimetrul terenului.

Pentru a începe curățenia, aceasta folosește o dronă de ultimă generație care plutește deasupra terenului și efectuează q scanări. O scanare este descrisă prin colțul stânga-sus de coordonate (is, js) și colțul dreapta-jos de coordonate (ij, jj). Din cauza unui defect, drona adaugă 1 la fiecare element din submatricea scanată.

ATENȚIE! Trixie poate să greșească și să aleagă colțul dreapta-jos în afara terenului. În acest caz, scanarea se aplică doar pe intersecția cu terenul:
i2 = min(ij, n), j2 = min(jj, m);
se adaugă 1 tuturor celulelor (i, j) cu is ≤ i ≤ i2 și js ≤ j ≤ j2;
dacă după tăiere rezultă un dreptunghi vid (adică is > i2 sau js > j2), scanarea nu are efect.

După ce toate scanările au fost aplicate, Trixie parcurge terenul și, pentru fiecare pereche de linii consecutive (i, i+1), cu 1 ≤ i ≤ n-1, procedează astfel: ia tile-urile alunecoase de pe linia i și tile-urile super-alunecoase de pe linia i+1, apoi înmulțește fiecare număr de pe tile-urile alunecoase cu fiecare număr de pe tile-urile super-alunecoase. Fiecare astfel de produs se numește nivel de alunecare și corespunde unui OMEGA-tile.

Un tile alunecos este definit ca un tile pe care este scris un număr prim. (Numerele 0 și 1 nu sunt prime.)

Un tile super-alunecos este definit ca un tile pe care este scris un număr aprim. Numim un număr aprim dacă acesta se poate scrie exact ca produsul a două numere prime distincte: x = p * q, unde p și q sunt prime și p ≠ q. (De exemplu 6=2*3 și 10=2*5 sunt aprime, dar 4=2*2 nu este aprim, iar 12=2*2*3 nu este aprim.)

Pentru o pereche de linii (i, i+1), notăm cu P mulțimea valorilor prime din linia i și cu S mulțimea valorilor aprime din linia i+1. Trixie formează toate OMEGA-tile-urile posibile, alegând orice p ∈ P și orice s ∈ S. Nivelul de alunecare este p * s.

Important: dacă există mai multe perechi (p, s) care dau același produs, acel produs apare de mai multe ori (se lucrează cu un multiset de produse).

Trixie își pune n - 1 întrebări (o întrebare pentru fiecare pereche de linii consecutive), de tipul:
„Care este nivelul de alunecare pentru al k-lea cel mai puțin alunecos OMEGA-tile?”
(adică al k-lea produs în ordine crescătoare).

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 de asemenea 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.