Lista de probleme 969

Se organizează cel mai grandios eveniment în aer liber pentru șoferi: Drive-in cinema cu o parcare imensă matriceală pentru mașini, cu patru ecrane imense la nord, sud, est și vest. Același film este proiectat în toate cele patru direcții. Altfel spus, ai la dispoziție 360° de film, deci, oricum ai parca, vei putea viziona filmul fără probleme consumând Tortilla chips cu gust de brânză și Coca-Cola.

Mașinile sosesc în parcare una după alta, având loc și timp suficient să efectueze manevre sigure de parcare. Însă, la finalul evenimentului, toate mașinile vor dori să plece cât mai repede. De aceea, este nevoie de o strategie prin care mașinile să părăsească parcarea în linie dreaptă (fără viraje), păstrând direcția în care erau așezate în timpul filmului, fără să se ciocnească cu alte mașini. Parcarea fiind într-o zonă deschisă, se poate ieși pe oriunde. Altfel spus: tot perimetrul matricei este ieșire. Organizatorii vă roagă să dați o mână de ajutor cu o strategie prin care să eliberați mașinile din parcare una câte una, precizând de fiecare dată coordonatele (linia și coloana) următoarei mașini care pleacă.

Cunoscând dimensiunile parcării N, M și direcția fiecărei mașini, se cere un plan de eliberare a tuturor mașinilor.

Se dă un arbore cu N noduri numerotate de la 1 la N, înrădăcinat în nodul 1. O mutare de cal dintr-un nod u către un nod v constă în parcurgerea unui traseu u → x → y → v, unde x este părintele lui u, y este părintele lui v, iar v este un fiu al lui y astfel încât v ≠ x. Observăm cum mutarea se aseamănă unei mutări de cal pe tabla de șah.

Date fiind N și părinții fiecărui nod P2, . . . , Pn (nodul 1, fiind rădăcina, nu are părinte), să se determine:

1. Numărul de noduri cu exact un fiu.

Date fiind, în plus, Q perechi de noduri, să se determine pentru fiecare pereche dată (a, b):

2. Dacă se poate ajunge din nodul a în nodul b făcând succesiv mutări de cal. În caz afirmativ, răspunsul va fi 1, altfel 0.
3. Numărul de trasee distincte ce pornesc din nodul a și ajung în nodul b făcând succesiv mutări de cal. Deoarece răspunsul poate fi destul de mare, se cere restul împărțirii acestuia la 109 + 7.

După o noapte furtunoasă, Gigel pleacă din crâșma satului, poziționată în punctul de coordonate (0, 0) și efectuează în ordine o succesiune alternativă de translații și rotații: tr1, rot1, tr2, rot2 …, trN, rotN în urma cărora ajunge la el acasă, în punctul de coordonate (a, b).

1. Date fiind N, șirul de translații tr1, tr2, …, trN, precum și șirul de rotații rot1, rot2 …, rotN, să se determine coordonatele casei lui Gigel (a, b).
2. Date fiind N, șirul de translații tr1, tr2, …, trN, precum și coordonatele casei lui Gigel (a, b), să se determine dacă există un șir de rotații rot1, rot2 …, rotN astfel încât în urma efectuării succesiunii de translații și rotații Gigel să ajungă la el acasă.
3. Date fiind N, șirul de translații tr1, tr2, …, trN, precum și coordonatele casei lui Gigel (a, b), să se determine un șir de rotații rot1, rot2 …, rotN astfel încât în urma efectuării succesiunii de translații și rotații Gigel să ajungă la el acasă.

Se dă o matrice de rebus cu n linii și m coloane. Fiecare celulă conține unul dintre caracterele:

• '+' – celulă blocată (nu poate conține literă)
• '-' – celulă liberă (trebuie completată cu o literă)

De asemenea, se dă o listă de W cuvinte (formate doar din litere mari A-Z) care trebuie completate în rebus.

Un cuvânt poate fi plasat:

• pe orizontală (în aceeași linie), sau
• pe verticală (în aceeași coloană),

într-un segment maximal de celule '-' consecutive (numit slot). Lungimea cuvântului trebuie să fie egală cu lungimea slotului.

Două cuvinte se pot intersecta (o celulă poate aparține atât unui slot orizontal, cât și unuia vertical), dar în acest caz litera rezultată în acea celulă trebuie să coincidă pentru ambele cuvinte.

Fiecare cuvânt din listă trebuie folosit exact o singură dată.

Fie G un graf neorientat conex cu N noduri și M muchii. Nodurile sunt numerotate de la 1 la N iar muchiile au asociate costuri numere naturale date. Un graf parţial al lui G conex şi fără cicluri este denumit arbore parţial. Costul unui arbore parțial este suma costurilor muchiilor arborelui. Deoarece unele muchii pot avea aceelași cost, este posibil ca graful G să aibă mai mulți arbori parțiali de cost minim. Definim o muchie a grafului G ca fiind esențială dacă ea face parte din toți arborii parțiali de cost minim ai lui G. Scrieţi un program care, cunoscând graful, rezolvă următoarele două cerinţe:
1. determină costul unui arbore parțial de cost minim al lui G;
2. determină numărul de muchii esențiale ale grafului G.

Să se scrie un program care, cunoscând numărul de tipuri de pietre preţioase N, valorile pietrelor preţioase v[1], v[2], …, v[N], numărul de camere de pe o linie/coloană P, precum şi camerele de pe linia P care au ieşire spre exterior, determină valoarea totală maximă a pietrelor preţioase pe care Gemini le poate acumula atunci când trece la nivelul următor (în condiţiile din joc).

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).

Se dă o matrice cu \(2\) linii și \(N\) coloane. De asemenea, se dau \(Q\) operații de \(2\) tipuri, pe care va trebui să le procesați în ordine. Cele \(2\) tipuri de operații sunt definite astfel:

• \(1\) \(lin\) \(col\) \(x\) – valoarea elementului aflat pe linia \(lin\) și coloana \(col\) va deveni \(x\).
• \(2\) \(st\) \(dr\) – afișați scorul submatricei cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\).

Scorul unei submatrice cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\) este calculat astfel:

1. Se pot permuta oricum coloanele submatricei. (Această permutare nu va persista la următoarele operații.)
2. După pasul anterior, se va alege un drum de lungime minimă cu capetele în celulele \((1,st)\), respectiv \((2,dr)\). Un drum este format dintr-o succesiune de celule distincte, unde oricare două celule consecutive din drum sunt adiacente pe linie sau pe coloană.
3. Scorul submatricei este egal cu valoarea minimă posibilă a medianei numerelor dintr-un drum construit la pasul anterior.

Definim mediana unui șir de numere \(A\) cu \(M\) elemente, numerotate de la \(1\) la \(M\), ca fiind elementul aflat pe poziția \(\lceil\frac{M}{2} \rceil\) în urma sortării șirului. De exemplu, mediana șirului \([1,3,1,2]\) este \(1\), iar mediana șirului \([1,2,3]\) este \(2\).

Se cere să se determine scorul submatricei date pentru fiecare operație de tip \(2\).

• 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.

Polygon este un joc pentru un singur jucător care începe pe un poligon cu N vârfuri. Scrieți un program care, dat fiind un poligon, calculează cel mai mare scor posibil și listează toate muchiile care, dacă sunt eliminate din prima mutare, pot conduce la un joc cu scorul maxim.