Lista de probleme 78

Filtrare

#865 Palat

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.

#3550 liceu

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

#3277 Lee

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.

Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită.

Simulare concurs CEX Hunedoara, februarie 2022

#3368 Lee2

Bil Gheiț, patronul Companiei Macrosoft, vă pune la dispoziție o matrice cu n linii și n coloane care memorează numere naturale. Un drum în matrice care pornește de la poziția (1,1) și se termină la poziția (n,n) este constituit din componente adiacente două câte două pe linii și coloane. Costul drumului este egal cu suma costurilor componentelor prin care trece drumul. Determinați costul minim al unui drum care pornește de la poziția (1,1) și se termină la poziția (n,n) și domnul Bil Gheiț vă vă angaja imediat la compania sa pe post de fochist.

#3949 mindist

Din fiecare celulă, să se afișeze distanța minimă la cel mai apropiat punct de referință.

Gigel este elev în clasa a XII-a la Liceul Teoretic “Ion Luca” din Vatra Dornei. Acesta, știind că urmează examenul de Bacalaureat și că nu a învățat nimic, s-a hotărât să plece de acasă să își găsească un rost în lume. După zile bune de mers, lipsit de energie, flămând și însetat, acesta a făcut un popas și s-a gândit că era mai bine să nu plece de acasă, motiv pentru care s-a hotărât să se întoarcă. Este cunoscut faptul că în pădurile dornene locuiesc atât Yeti, cât și Bigfoot, precum și mulți vârcolaci. Gigel, fiind un dornean adevărat, cunoaște coordonatele zonelor unde aceștia locuiesc și dorește să se întoarcă acasă pe drumul cel mai scurt, evitându-i pe aceștia.

Cunoscând suprafața regiunii în care se află Gigel și casa acestuia (care poate fi reprezentată printr-un tablou bidimensional cu n linii și m coloane, în care fiecare zonă are coordonatele x și y), coordonatele casei (X1, Y1) și coordonatele locului de popas (X2, Y2), coordonatele zonelor în care locuiesc Yeti (XY, YY) și Bigfoot (XB, YB), precum și coordonatele (X, Y) ale celor K zone în care locuiesc vârcolacii, se cere să îl ajutați pe Gigel să găsească lungimea D a celui mai scurt drum spre casă.

#3114 abq

Fie o matrice cu n linii (numerotate de la 1 la n) și m coloane (numerotate de la 1 la m) ce conține doar literele a și b. Se definește un drum de la o poziție (xs, ys) la o alta (xf, yf) ca fiind o succesiune de pași care pornește din coordonatele (xs, ys) și ajunge în (xf, yf) și care trece numai prin componente care memorează litera a. La fiecare pas, de la o poziţie (i, j) se poate trece într-una din poziţiile (i+1, j), (i-1, j), (i, j+1), (i, j-1). Lungimea drumului este dată de numărul de componente care compun drumul.

Având la dispoziție q întrebări date sub forma a patru numere naturale xs ys xf yf, trebuie să răspundeți pentru fiecare întrebare care este lungimea minimă a unui drum de la (xs, ys) la (xf, yf) care trece numai prin componente ce memorează litera a. Dacă un astfel de drum nu există, veți afișa valoarea –1.