Lista de probleme 41

Filtrare

Dificultate

Operații intrare/ieșire

#876 Coada

Să se scrie un program care gestionează o coadă de numere întregi. Inițial coada este vidă. Programul va citi de la tastatură o listă de operații, care pot fi:

  • push X – adaugă valoarea întreagă X în coadă;
  • pop – elimină elementul din coadă;
  • front – afișează elementul de la începutul cozii.

Programul va realiza asupra cozii operațiile citite, în ordine. Afișările se fac pe ecran, câte o valoare pe linie.

#1598 Coada1

Se consideră C o coadă de numere naturale, iniţial vidă. Se definesc 2 tipuri de operaţii.

Operaţia 1 : push X, adaugă elementul X în coadă. Dacă X există deja în coadă, se scot toate elementele din coadă, pana la întâlnirea lui, inclusiv X.

Exemplu: 
	C: 2 4 5 1 6
	Push 5
	C: 1 6 5 ( s-au scos 2, 4, 5).

Operaţia 2: query X, cere afişarea poziţiei elementului X în coada C. Dacă elementul nu există în coadă, se afişează -1.

Exemplu:
	C: 2 5 1 3 7
	Query 1
	Răspuns: 3

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

Imaginație personală

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

OJI 2003

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

Se dau patru numere naturale n a x y. Să se afișeze elementele mulțimii M, cu următoarele proprietăți:

  • toate elementele lui M sunt numere naturale mai mici sau egale cu n;
  • a se află în M;
  • dacă b se află în M, atunci b+x și b+y se află în M.

#882 Lac

Se dă harta unui lac de formă dreptunghiulară, împărțit în n*m zone dispuse sub forma unei matrice cu n linii și m coloane. Zonele pot fi acoperite cu apă, sau pot fi zone de uscat. Zonele de uscat care sunt învecinate pe linie sau pe coloană formează insule sau peninsule. Peninsule conțin cel puțin o zonă de uscat pe marginea lacului (matricei), în timp ce insulele sunt situate în întregime în interiorul lacului.

Cunoscând harta lacului, determinați numărul de insule și numărul de peninsule.

Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, reprezentând planul unui teren în care 0 reprezintă o zonă accesibilă, iar 1 reprezintă o zonă inaccesibilă. O zonă a terenului are ca și coordonate linia și coloana corespunzătoare din matrice. Într-o zonă cunoscută a matricei se află un robot, iar în altă zonă, e asemenea cunoscută, se află o roboțică. Determinați numărul minim de pași prin care robotul va ajunge la roboțică. Dacă nu este posibil ca robotul să ajungă la roboțică, rezultatul va fi -1.

#866 Acces

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 una dintre camere se află proprietarul clădirii, care dorește să afle, pentru fiecare dintre camere care este timpul minim necesar pentru a ajunge în acea cameră.

Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu n linii și m coloane, formată din n*m zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană.

Un călător dorește să traverseze deșertul de la nord (prima linie) la sud(ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesibilă de pe prima line și dorește să ajungă pe ultima linie cu număr minim de pași.