Lista de probleme 92

Filtrare

Dificultate

Operații intrare/ieșire

Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:

  • termenul i al sumei se află pe linia i din triunghi
  • pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mare sumă care se poate obține în acest mod.

Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:

  • termenul i al sumei se află pe linia i din triunghi
  • pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mică sumă care se poate obține în acest mod și numerele care o alcătuiesc.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. În fiecare cameră se află o cantitate cunoscută de bomboane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1), fără a părăsi clădirea.

Un copil intră în clădire, parcurge un șir de camere după regula precizată și iese din clădire, luând din fiecare cameră în care intră toate bomboanele existente. Determinați cantitatea maximă de bomboane care poate fi culeasă precum și un traseu prin clădire în care se adună cantitatea maximă de bomboane.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Pentru a intra într-o cameră se plătește o sumă cunoscută. Intrarea în clădire este în camera de coordonate (n,1), iar ieșirea în camera de coordonate (1,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i-1,j) sau (i,j+1), fără a părăsi clădirea.

O persoană intră în clădire, parcurge un șir de camere după regula precizată și iese din clădire, plătind în fiecare cameră taxa corespunzătoare. Determinați suma minimă care trebuie plătită.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Pentru a intra într-o cameră se plătește o sumă cunoscută, exprimată în lei. Intrarea în clădire este în camera de coordonate (1,m), iar ieșirea în camera de coordonate (n,1). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j-1), fără a părăsi clădirea.

Dom’ Profesor intră în clădire având asupra lui o sumă S, parcurge un șir de camere după regula precizată și iese din clădire, plătind în fiecare cameră taxa corespunzătoare. Determinați suma maximă pe care o poate avea persoana după ce iese din clădire.

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. În fiecare sector se află o comoară ascunsă de Ali Baba. Se cunoaște valoarea în galbeni a fiecărei comori.

Un călător trebuie să traverseze deșertul de la Nord la Sud, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul colectează comoara din acel sector.

Determinați valoarea totală maximă a comorilor pe care le poate colecta călătorul la traversarea deșertului, știind că pleacă din orice sector al liniei 1 și se oprește în orice sector al linei n, cu respectarea condițiilor de mai sus.

#432 Taxe

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. Intrarea într-un sector se plătește cu o taxă cunoscută, exprimată în galbeni.

Un călător trebuie să traverseze deșertul de la Est la Vest, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i-1,j-1), (i,j-1) sau (i+1,j-1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul plătește taxa aferentă acelui sector.

Determinați suma totală minimă pe care trebuie să o plătească călătorul la traversarea deșertului, știind că pleacă din orice sector al coloanei m (Est) și se oprește în orice sector al coloanei 1 (Vest), cu respectarea condițiilor de mai sus.

#1597 Vizita

După ce în problema Plata şi-a cumpărat biscuiţi, iar în problema Maraton şi-a făcut temele, Costy s-a hotărât să meargă în vizită la prietenul său Paul. Și pentru că Paul este prietenul său cel mai bun, bineînţeles că nu se va duce cu mâna goala. Va trece pe la magazin şi îi va cumpăra un pachet de biscuiţi. Marea problemă a eroului nostru este oraşul rău famat, la fiecare intersecţie existând pericole. Oraşul are forma de două triunghiuri dreptunghice isoscele cu un vârf comun, ca în figura următoare:

C 
X X
X X X
X X X B
      X X
      X X X
      X X X P 

C – reprezintă poziţia iniţială a lui Costy, care se va afla mereu în colţul din stânga sus.
B – reprezintă poziţia magazinului, care se va afla mereu în vârful comun al celor 2
triunghiuri.
P – reprezintă poziţia lui Paul, care se va afla mereu în colţul din dreapta jos.

Cum spuneam, la fiecare intersecţie există pericole. O intersecţie X[i][j] reprezintă intersecţia străzii orizontale i, cu strada verticală j. Gradul de periculozitate al unei intersecţii este un număr întreg X[i][j]. Definim gradul unui drum ca fiind suma gradelor intersecţiilor ce compun acel drum.

Costy poate merge de la o intersecţie X[i][j], doar la o intersecţie X[i][j + 1] (în dreapta) sau X[i + 1][j](în jos).

#396 SCLM

Se dă un șir n numere naturale. Determinați un cel mai lung subșir crescător al șirului.

De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește să taie anumiți plopi, astfel încât înălțimile celor rămași să fie în ordine strict descrescătoare.

Determinați numărul minim de plopi care trebuie tăiați astfel încât înălțimile celor rămași să fie în ordine strict descrescătoare.