Lista de probleme 140

Ileana Cosânzeana se mărită. În consecință a dat sfoară-n țară și au venit mai mulți Feți-Frumoși, dornici să primească mâna fetei, împreună cu palatul în care locuiește. Acesta este alcătuit din n*m camere, dispuse sub forma unei matrice cu n linii și m coloane.

În anumite camere nu se poate intra, deoarece acolo se află zmei răi. În celelalte se poate intra; mai precis se poate trece dintr-o cameră în altă cameră dacă se învecinează pe linie sau pe coloană. În una dintre camere se află Ileana Cosânzeana, iar în alte camere se afla câte un Făt-Frumos. Aceștia pot trece dintr-o cameră în alta, cu condiția să nu intre într-o cameră care conține un zmeu. Trecerea dintr-o cameră în alta a unui Făt-Frumos durează un minut.

Alegerea celui care va primi mâna Ilenei se face pe principiul primul venit, primul servit (suntem la capitolul Coada). Mai precis, se va căsători cu Ileana Cosânzeana acel Făt Frumos care ajunge primul la ea. Dacă ajung la Ileana Cosânzeana mai mulți Feți-Frumoși în același timp, deoarece este interzisă poligamia, Ileana se va căsători cu Făt-Frumos care la început era situat cât mai jos (pe o linie cu indice cât mai mare) și cât mai la dreapta (pe o coloană cu indice cât mai mare).

Aflați poziția inițială a lui Făt-Frumos care va primi mâna fetei.

Marciuc este un băiat foarte neastâmpărat. El refuză să învețe informatică, așa că înainte de fiecare oră el pleacă pentru a explora noul său liceu. La plecare le promite colegilor lui că o să treacă pe la magazin înainte de a se întoarce în clasă, pentru a avea ce să mănânce în pauza următoare. Însă, dacă va ajunge în clasă în mai mult de T secunde, va întarza la ora așa că în acest caz va folosi o ruta directă spre clasă.

Liceul poate fi reprezentat sub forma unei matrice cu n linii și n coloane. Există 3 tipuri de celule:

• celulă liberă, pe unde băiatul poate avansa, o mutare durând o secundă;
• celulă ocupată de un zid, pe unde băiatul nu poate avansa;
• celulă în care se află o scurtătură, ce îl duce într-o secundă de la poziția, x1 y1, la poziția x2 y2 sau invers;

Fiind dat numărul n de linii și de coloane, coordonatele celulelor ocupate de zid și coordonatele scurtăturilor, se cere să se afișeze numărul de secunde în care Marciuc reușește să ajungă în clasă, trecând și pe la magazin. Dacă magazinul nu este accesibil sau daca va ajunge în clasă in mai mult de T secunde, atunci el nu va mai merge la magazin și se va afișa numărul de secunde în care acesta ajunge de la poziția lui la clasă. De asemenea, se va afișa și traseul folosit.

Se consideră un cuvânt format numai din litere mici și un număr natural nenul K. Să se determine cuvântul minim lexicografic obținut prin eliminarea a exact K litere din cuvântul inițial.

Pentru că e criză, cu ocazia campaniei electorale, în loc de găleți pline cu făină, zahăr și bilete la teatru primiți un șir a1, a2, …, an care reprezintă o permutare a mulțimii {1,2,...,n}. Pentru fiecare secvență nevidă a permutării costul ei este valoarea maximă din acea secvență. Să se calculeze suma totală a costurilor tuturor secvențelor.

Se consideră o clădire de formă dreptunghiulară, împărțită în n*m camere, dispuse sub forma unei matrice cu n linii și m coloane. Dintr-o cameră se poate trece în oricare dintre cele 4 camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

În anumite camere se află echipe de pompieri. Pentru o intervenție cât mai rapidă în caz de incendiu în una dintre camerele clădirii, este necesar să se știe, pentru fiecare cameră care este timpul minim în care o echipă de pompieri ajunge în acea cameră.

Se dă un șir cu n elemente, numere naturale. Să se afișeze, pentru fiecare element din șir, valoarea din șir aflată după acesta și mai mare decât acesta. Dacă o asemenea valoare nu există, se va afișa -1.

Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.

Se dă un număr natural N si un șir v de N numere naturale. Sa se răspundă la Q întrebări de tipul:

• D y: Care este cea mai mică poziție x, unde x > y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi N + 1.
• S y: Care este cea mai mare poziție x, unde x < y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi 0.

Se consideră o matrice cu N linii și N coloane, numerotate de la 1 la N, care memorează doar valori 0 și 1. Se dau de asemenea coordonatele a trei componente din această matrice. Să se determine lungimea minimă a unui drum care pleacă din poziția (1,1), trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția (N, N), drum care trece doar prin componente marcate cu 0 și învecinate pe linii și coloane.

Se dă un șir a1, a2, …, an de numere întregi și m operații, fiecare operație fiind dată printr-o pereche de numere op și k: dacă op = 1 atunci primele k elemente din șir se ordonează crescător, iar dacă op = 2 atunci primele k elemente din șir se ordonează descrescător. Să se afișeze elementele șirului după efectuarea tuturor celor m operații.