Lista de probleme 1033

Se consideră o pereche de șiruri de caractere, 𝑆 și 𝑇 , de lungime 𝑛, respectiv 𝑚, formate exclusiv din litere mici ale alfabetului englez. Pozițiile literelor sunt numerotate în șir începând de la 1.

Sunt două tipuri de operații ce se pot efectua asupra șirului 𝑇:

• 1 𝑝: se șterge litera de pe poziția 𝑝;
• 2 𝑠𝑡 𝑑𝑟 (cu 𝑠𝑡 ≤ 𝑑𝑟): se sortează crescător (alfabetic) literele din subsecvența ce corespunde intervalului de poziții [𝑠𝑡, 𝑑𝑟];

unde 𝑝, 𝑠𝑡 și 𝑑𝑟 sunt poziții ale unor litere din șirul 𝑇.

Inițial, toate literele șirului 𝑇 sunt necolorate. O operație de tip 2 poate fi realizată doar dacă toate literele din subsecvența corespunzătoare intervalului de poziții [𝑠𝑡,𝑑𝑟] sunt necolorate. După efectuarea sortării, toate literele din această subsecvență devin colorate.

Pentru fiecare dintre perechile de șiruri de tipul 𝑆 și 𝑇 date:

1. Să se afișeze literele distincte care apar în cel puțin unul dintre șiruri și, pentru fiecare dintre acestea, sim-
   bolul șirului (literele 𝑆 sau 𝑇) în care apare de mai multe ori. În caz de egalitate, se alege șirul 𝑇.
2. Să se determine o succesiune de operații de tipul 1 și/sau 2 ce pot fi aplicate șirului 𝑇, care să îl transforme
   într-un șir egal cu 𝑆. Să se afișeze DA în cazul în care există o astfel de succesiune de operații, sau NU în
   caz contrar.

În Tărâmul Magic al Insulelor, se desfășoară o vânătoare anuală de comori, unde echipele explorează insule fermecate, delimitate de apa ce le înconjoară. La ordinul regelui A., sunt ascunse comori pe fiecare insulă. Harta tărâmului este reprezentată sub forma unei matrice de dimensiune 𝑛 × 𝑚, ale cărei elemente codifică zone pătratice, cu latura de 1 metru. Acestea pot fi:

• zonă care conține apă, marcată cu −1;
• zonă care conține doar pământ, marcată cu 0; sau
• zonă care conține pământ și o singură comoară, marcată cu un număr natural nenul.

Două zone se consideră vecine dacă au o latură comună. Două zone aparţin aceleiaşi insule dacă ele sunt vecine sau dacă se poate ajunge de la o zonă la cealaltă pe un drum care parcurge o succesiune de zone, oricare două zone parcurse consecutiv fiind vecine. În acest an, căpitanul Poseidon dorește să facă o farsă regelui A., permutând comorile, astfel încât fiecare comoară să fie mutată într-o zona în care inițial a fost o altă comoară. Totuși, pentru a nu atrage atenția prea mult, comorile vor rămâne în cadrul insulei pe care se aflau inițial

Pentru început, căpitanul Poseidon își propune să rezolve următoarele cerințe:

1. Câte comori se găsesc pe insula pe care se află căpitanul Poseidon?
2. Câte soluții există pentru plasarea tuturor comorilor, astfel încât fiecare comoară să fie mutată în cadrul aceleiași insule, într-o zonă în care inițial a fost o altă comoară? Pentru că numărul de soluții poate fi foarte mare, răspunsul va fi afișat modulo 1 000 000 007.

Mark a construit o parcare dreptunghiulară, pe care a împărțit-o, utilizând marcaje, în locuri de parcare pătrate, organizate pe n linii (numerotate de la 1 la n) și m coloane (numerotate de la 1 la m). Astfel, un loc de parcare poate fi identificat prin numărul liniei şi numărul coloanei pe care acesta se află. Orice mașină poate fi parcată în interiorul unui loc de parcare, paralel cu liniile orizontale de marcaj, sau paralel cu liniile verticale, fără a depăși conturul pătratului corespunzător.
Scrieți un program care, cunoscând dimensiunile parcării, pozițiile întreruperilor din zid, numărul de mașini, iar pentru fiecare mașină numărul liniei și al coloanei corespunzătoare locului în care este parcată și modul de parcare a acesteia, rezolvă următoarele două cerinţe:
1) determină numărul de mașini care pot ieși din parcare fără a fi condiționate de mutarea sau de părăsirea parcării de către alte mașini (numărul de maşini care pot ieşi în prima serie);
2) determină numărul total maşini care pot ieşi din parcare, precum şi numărul de serii în care se realizează ieşirea tuturor acestor maşini.

O pereche de șiruri de caractere S și T, formate doar din literele A, B și C, este egalabilă dacă șirurile pot deveni egale după o transfomare constând din aplicarea unei succesiuni formate din 0 sau mai multe operații. O operație constă din inserarea sau ștergerea din unul dintre șiruri a uneia dintre subsecvențele: AAA, BBB, CCC, ABC sau BAC. Atât inserarea, cât și ștergerea se pot realiza de pe orice poziție. În urma unei operații este posibil ca șirul rezultat să devină vid. Pentru o succesiune dată de perechi de șiruri, să se determine, pentru fiecare pereche, dacă este egalabilă.

Doamna profesoară de limba română i-a recomandat lui Tedi să citească “Legendele Olimpului”. Săptămâna trecută ea a citit legenda lui Tezeu și a Minotaurului. În aceasta, eroul Tezeu hotărăște să intre în labirintul ce ascunde legendara bestie pe jumătate om și pe jumătate taur, Minotaurul, cu scopul de a-l ucide și de a câștiga mâna prințesei cretane, Ariadna. Labirintul Minotaurului este fermecat, deoarece este construit de sculptorul Dedal după niște reguli recursive. labirintului, începând din colțul din stânga jos al matricei, adică din celula cu coordonatele (2N, 1). Cunoscându-se N și P, ajutați-l pe Tezeu să afle linia și coloana celulei în care se află Minotaurul.

Scrieţi un program care, cunoscând n şi m (dimensiunile picturii), respectiv înălţimile pixelilor 3D, rezolvă următoarele trei cerinţe:
1. determină numărul maxim de culori pure care se combină pe un pixel 3D;
2. determină numărul de culori distincte care apar în pictura creată conform algoritmului aplicat de robotul Vasile;
3. determină dimensiunea maximă a unei zone formată din pixeli 3D de aceeaşi culoare, diferită de alb.

Se dă o matrice cu 2 linii si n coloane care are k celule ocupate. Se dau q interogări de forma (x1, y1, x2, y2), cu următoarea semnificație: dacă se ocupă două celule libere distincte ale matricii inițiale, (x1, y1) și (x2, y2), se poate pava complet matricea cu piese de domino de dimensiuni 2 x 1 și 1 x 2? După efectuarea unei interogări celulele ocupate asociate acesteia vor deveni din nou libere (modificările aduse matricei nu persistă între interogări). Să se determine, pentru fiecare interogare, dacă este posibil ca matricea să fie pavată complet cu piese de domino de dimensiuni 2 x 1 și 1 x 2.

Profesorul de informatică trebuie să corecteze tezele a m elevi. Elevii au avut de rezolvat n probleme în teză, numerotate de la 1 la n. Fiecare elev a rezolvat toate problemele, deci profesorul are de corectat în total m x n probleme. La începerea corectării fiecărei teze, trebuie identificat numele elevului, proces care durează exact p secunde de fiecare dată, chiar dacă se revine la aceeași teză de mai multe ori.
După începerea corectării unei teze, căutarea fiecărei probleme durează k secunde. Corectarea primei probleme din submulțimea aleasă durează t[1] secunde, corectarea celei de-a doua probleme durează t[2] secunde ș.a.m.d. Se garantează că t[1] < t[2] < ... < t[n]. De fiecare dată când se revine la o anumită teză și se reîncepe corectarea ei cu o altă submulțime de probleme, corectarea primei probleme din submulțime va dura din nou t[1] secunde.
Să se determine timpul minim în care pot fi corectate cele m lucrări.

Adrian și-a luat un elicopter. Evident, un elicopter de jucărie. Adrian se joacă cu elicopterul său pe o suprafață reprezentată de o matrice de n×m, unde se află turnuri. Fiecare turn se află în celula reprezentată de indicii i și j, având înălțimea h[i][j]. În jocul său, Adrian dorește să piloteze elicopterul său. Inițial, elicopterul este ridicat în aer la o anumită înălțime, și poziționat într-o celulă aflată pe prima coloană. Pe parcursul jocului, elicopterul este menținut la înălțimea inițială. La fiecare pas, elicopterul se poate muta în una din celulele învecinate pe linie sau pe coloană, în stânga, dreapta, sus sau jos, doar dacă înălțimea turnului nu este mai mare decât înălțimea la care se află elicopterul. Jocul se termină când elicopterul ajunge într-o celulă aflată pe ultima coloană.

Să se determine cea mai mică valoare a înălțimii la care trebuie ridicat elicopterul, astfel încât acesta să poată ajunge pe o celulă aflată pe ultima coloană.

Un institut de istorie colectează obiecte descoperite pe mai multe șantiere arheologice. Pentru fiecare descoperire de pe șantier se stabilește categoria din care face parte obiectul (de exemplu: ceramică, monedă etc.), materialul din care este confecționat și numărul de exemplare ce fac parte din aceeași categorie și au același material. Categoria și materialul unui obiect sunt reprezentate prin numere naturale nenule.
Scrieţi un program care determină și afișează pentru datele trimise de n șantiere către institut:
1. Lista obiectelor în ordine crescătoare după categorie: se va afișa categoria și numărul total de exemplare descoperite pe toate șantierele la acea categorie.
2. Lista obiectelor descoperite în ordine crescătoare după categorie: pentru fiecare obiect se afișează categoria, materialul și numărul de exemplare descoperite, ce au aceste caracteristici.