Lista de probleme 23

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

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.

Calculați lungimea drumului minim de la locul de popas al lui Gigel la casa acestuia, ocolind vârcolacii, pe Yeti și pe Bigfoot.

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

#3380 Castel2

Se consideră un castel de formă dreptunghiulară, alcătuit din n*m camere dispuse pe n linii și m coloane. Intrarea în castel este în camera de coordonate (1,1), ieșirea în camera de coordonate n,m, unele camere sunt închise, dintr-o cameră se poate trece în camerele învecinate pe linie și pe coloană, iar unele camere sunt ocupate de zmei gripați, fiecare zmeu afectând camera sa și camere aflate în jurul său la distanța mai mică sau egală cu k.

Pentru a câștiga inima Ilenei Cosânzeana, Făt-Frumos trebuie să traverseze castelul. Deoarece nu se pricepe la informatică vă roagă pe voi să determinați care este lungimea minimă a unui traseu care traversează castelul, trece doar prin camere deschise și nu trece prin camere afectate de zmei.

#1856 Taxe2

Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.

Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune n•n. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

Ştiind că el are în buzunar S euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

#1871 UbuPH

Într-o zi telefonul lui Max s-a stricat.Văzând o reclamă la noul telefon cu sistemul de operare Ubuntu, s-a gândit să achiziționeze și el unul.

Drumul de la casa lui la magazin poate fi reprezentat ca o matrice cu n linii și m coloane. În fiecare element al matricei este o barieră; pentru a trece de bariere trebuie plătită o sumă de bani, care nu este aceeași pentru fiecare barieră și poate fi chiar 0.

Casa lui se află pe coordonatele (ic,jc), iar magazinul la coordonatele (im,jm).
Pentru că trebuie să cumpere telefonul, este nevoie ca drumul lui sa fie cât mai puțin costisitor, plătind la bariere o sumă totală minimă.

Hackerul Gigel e pus pe șotii. El încearcă să suprasolicite o rețea de calculatoare cu un pachet de date corupt. Ajutați-l să paseze la inifinit pachetul între calculatoare!

Zoli și D’Umbră se pierd din nou prin labirint.

#2390 rj

În ultima ecranizare a celebrei piese shakespeariene Romeo și Julieta trăiesc într-un oraș modern, comunică prin e-mail și chiar învață să programeze. Într-o secvență tulburătoare sunt prezentate frământările interioare ale celor doi eroi încercând fără succes să scrie un program care să determine un punct optim de întâlnire.
Ei au analizat harta orașului și au reprezentat-o sub forma unei matrice cu N linii şi M coloane, în matrice fiind marcate cu spațiu zonele prin care se poate trece (străzi lipsite de pericole) şi cu X zonele prin care nu se poate trece. De asemenea, în matrice au marcat cu R locul în care se află locuința lui Romeo, iar cu J locul în care se află locuința Julietei. Ei se pot deplasa numai prin zonele care sunt marcate cu spaţiu, din poziţia curentă în oricare dintre cele 8 poziţii învecinate (pe orizontală, verticală sau diagonale).
Cum lui Romeo nu îi place să aştepte şi nici să se lase aşteptat n-ar fi tocmai bine, ei au hotărât că trebuie să aleagă un punct de întâlnire în care atât Romeo, cât şi Julieta să poată ajunge în acelaşi timp, plecând de acasă. Fiindcă la întâlniri amândoi vin într-un suflet, ei estimează timpul necesar pentru a ajunge la întâlnire prin numărul de elemente din matrice care constituie drumul cel mai scurt de acasă până la punctul de întâlnire. Şi cum probabil există mai multe puncte de întâlnire posibile, ei vor să îl aleagă pe cel în care timpul necesar pentru a ajunge la punctul de întâlnire este minim.
Scrieţi un program care să determine o poziţie pe hartă la care Romeo şi Julieta pot să ajungă în acelaşi timp. Dacă există mai multe soluţii, programul trebuie să determine o soluţie pentru care timpul este minim.

#1538 SudEst

Fermierul Ion deţine un teren de formă pătrată, împărţit în NxN pătrate de latură unitate, pe care cultivă cartofi. Pentru recoltarea cartofilor fermierul foloseşte un robot special proiectat în acest scop. Robotul porneşte din pătratul din stânga sus, de coordonate (1,1) şi trebuie să ajungă în pătratul din dreapta jos, de coordonate (N, N). Traseul robotului este programat prin memorarea unor comenzi pe o cartelă magnetică. Fiecare comandă specifică direcţia de deplasare (sud sau est) şi numărul de pătrate pe care le parcurge în direcţia respectivă. Robotul strânge recolta doar din pătratele în care se opreşte între două comenzi.

Din păcate, cartela pe care se află programul s-a deteriorat şi unitatea de citire a robotului nu mai poate distinge direcţia de deplasare, ci numai numărul de paşi pe care trebuie să-i facă robotul la fiecare comandă. Fermierul Ion trebuie să introducă manual, pentru fiecare comandă, direcţia de deplasare.

Scrieţi un program care să determine cantitatea maximă de cartofi pe care o poate culege robotul, în ipoteza în care Ion specifică manual, pentru fiecare comandă, direcţia urmată de robot. Se va determina şi traseul pe care se obţine la recolta maximă.