Probleme de informatica - enunturi si rezolvari

Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (111)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (50)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (86)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (40)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (14)
Programare vizuală în C# (19)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)

Programare dinamica

#822. [2017-01-25 - 09:18:11]
Se citeste un numar natural n (2<=n<=20) si apoi o matrice cu n linii si n coloane având elementele numere întregi cu cel mult 4 cifre fiecare. Parcurgerea matricii se face din coltul (n,1) spre coltul (1,n) si se poate face pe directiile: nord, nord-est si est.
a) Afisati numarul de moduri în care se poate ajunge din coltul (n,1) în coltul (1,n).
b) Afisati suma maxima care se poate obtine parcurgând matricea din coltul (n,1) în coltul (1,n).
Pentru citire se va folosi fisierul 2.in, iar pentru afisare fisierul 2.out.
Exemplu:
2.in
3
1 2 3
-1 3 4
2 -1 -1
2.out
13
12
Rezolvare

#821. [2017-01-25 - 09:12:37]
Se citesc doua numere naturale n si m (1<=m,n<=100) si apoi o matrice cu n linii si m coloane având elementele numere întregi cu cel mult 4 cifre fiecare. Afisati pentru fiecare coloana a matricii numarul de elemente al celui mai lung subsir strict crescator care se poate forma parcurgând elementele coloanei de sus în jos. Pentru citire se va folosi fisierul 1.in, iar pentru afisare fi?ierul 1.out.
Exemplu:
1.in
4 4
1 4 2 3
2 9 8 7
3 6 3 8
1 2 3 3
1.out
3 2 2 3
Rezolvare


#750. [2015-11-11 - 08:55:57]
O livada este impartita in nXm zone. In fiecare zona creste cate un pom. Din fiecare pom cade pe jos o cantitate de fructe.
In zona stanga sus se afla un arici care vrea sa ajunga in zona dreapta jos. Ariciul se poate deplasa doar pe doua directii: in jos sau spre dreapta.
Determinati cantitatea maxima de fructe pe care le poate aduna ariciul prin deplasarea din pozitia initiala in cea dorita.
Citirea se face din fisierul arici.in care contine pe prima linie dimensiunile livezii, adica n si m, si apoi cantitatea de fructe din fiecare dintre cele nXm zone.
Afisarea cantitatii maxime de fructe se va face in fisierul arici.out.
Exemplu:
arici.in
3 3
0 4 1
0 1 1
1 0 1
arici.out
7
Rezolvare

#738. [2015-11-10 - 22:51:39]
Din fisierul nrsubsircresc.in se citeste un numar natural n(n<=300) si apoi un sir cu n elemente numere naturale cu cel mult 9 cifre fiecare.
Calculati si afisati in fisierul nrsubsircresc.out numarul de subsiruri strict crescatoare care se pot forma in sirul citit.
Exeplu:
nrsubsircresc.in
5
1 2 3 4 2
nrsubsircresc.out
17
Explicatie: subsirurile strict crescatoare sunt:
1
2
3
4
2
1 2
1 3
1 4
1 2
2 3
2 4
3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2 3 4
Rezolvare

#736. [2015-11-10 - 22:51:18]
Calculul combinarilor de n luate cate k folosind numere mari.
Rezolvare

#421. [2013-02-10 - 09:13:06]
Se da o matrice patratica de ordin n care contine numere naturale si care are liniile si coloanele numerotate de la 1 la n. Se citeste apoi un numar natural m si n perechi de pozitii din matrice de forma (i1, j1) si (i2,j2) astfel incat i1 sa fie mai mic decat i2 si j1 sa fie mai mic decat j2.
Calculati si afisati pentru fiecare pereche de pozitii suma elementelor din matrice aflate in submatricea care are coltul stanga-sus in (i1,j1) si coltul dreapta-jos in (i2,j2).
Exemplu:
date.in
3
1 2 1
3 6 1
1 3 6
3
2 2 3 3
2 1 3 3
1 1 1 3
date.out
16 20 4
Rezolvare

#408. [2012-12-19 - 09:37:17]
Cladirea Finantelor publice este formata din birouri dispuse intr-un dreptunghi cu nXm elemente. Intre doua birouri se poate trece daca sunt alaturate pe linie sau pe coloana.
Pentru fiecare birou se cunoaste valoare taxei care trebuie platita in acel birou (valoare naturala). Un contribuabil intra in cladire prin biroul 1,1 si trebuie sa o parareasca prin biroul n,m. Calculati suma minima a taxelor pe care le poate plati contribuabilul de la intrare pana la iesirea din cladire.
Exemplu:
n=4, m=3, dispunerea birourilor si taxa din fiecare:
3 7 2
6 4 3
6 3 1
6 2 2
Valoarea minima pe care o poate plati contribuabilul este 18 (corespunde parcurgerii birourilor cu taxele: 3 7 2 3 1 2)
Rezolvare

#407. [2012-12-12 - 11:36:04]
O tabla de sah se citeste ca o matrice n*n in care pozitiile libere au valoarea 0, iar piesele sunt marcate prin valoarea 1.
Sa se determine drumul pe care poate ajunge un pion de pe prima linie pe ultima linie luand un numar maxim de piese. Pe prima linie nu sunt piese si pionul poate porni din orice pozitie de pe prima linie
Pozitia initiala a pionului se considera libera.
Pionul aflat in pozitia i,j se poate deplasa astfel:
- in pozitia i+1,j daca e libera
- in pozitia i+1, j-1 daca e piesa in aceasta pozitie
- in pozitia i+1, j+1 daca e piesa in aceasta pozitie

Exemplu:
5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 1
0 0 0 1 1
0 1 0 1 1

Drumul optim este:
1 1
2 2
3 3
4 4
5 5
Pe acest drum pionul ia 4 piese.
Rezolvare

#406. [2012-12-12 - 08:44:32]
Se citeste un numar n si apoi 2 siruri formate din cate n cuvinte fiecare. Primul sir de cuvinte stabileste ordinea initiala, iar al doilea este o permutare a primului (aceleasi cuvinte, dar in alta ordine).
Gasiti cel mai lung subsir de cuvinte din cel de-al doilea sir care are proprietatea ca are cuvintele in ordinea din primul sir de cuvinte. Se va afisa numarul maxim de cuvinte si apoi cuvintele.
Daca exista mai multe subsiruri de lungime maxima se va afisa unul dintre ele.
Exemplu:
date.in
5
platon kant marx stalin havel
marx stalin kant platon havel
date.out
3
marx stalin havel
Rezolvare

#405. [2012-12-12 - 08:40:39]
Subsir crescator maximal.
Se citeste un numar n si apoi un sir de n numere intregi. Gasiti cel mai lung subsir al sirului citit care are proprietatea ca elementele sunt in ordine crescatoare.
Daca exista mai multe subsiruri de lungime maxima se va afisa unul dintre ele.
Exemplu:
date.in
9
4 2 3 0 5 2 6 9 8
date.out
2 3 5 6 9
Rezolvare

#403. [2012-12-06 - 11:51:30]
Se citeste un numar natural n si apoi un vector cu n elemente numere intregi. Determinati secventa din vector care are suma elementelor maxima.
Exemplu:
n=9
-2 1 -3 3 -1 4 -6 2 3
secventa de suma maxima este 3 -1 4 si are suma 6
Rezolvare

#402. [2012-12-06 - 10:31:09]
Un paianjen a tesut o panza de forma dreptunghiulara formata din n linii orizontale si m linii verticale.
Calculati in cate moduri poate el merge din coltul stanga-sus in coltul dreapta-jos facand un numar minim de pasi. (n+m-2)
Exemple:
pentru n=3 si m=3 exista 6 moduri
pentru n=1 si m=5 exista un singur mod
Rezolvare

#401. [2012-12-06 - 00:01:07]
Calculati cate submultimi cu k elemente are o multime cu n elemente.
Rezolvare

#400. [2012-12-05 - 23:21:12]
Se citeste o matrice patratica de ordin n formata din numere naturale.
Se calculeaza sume pornind de pe prima linie prin deplasari pe linia urmatoare in unul dintre cei 3 vecini de pe aceeasi coloana sau de pe cele 2 alaturate. Gasiti suma maxima care se poate calcula astfel si care sunt valorile din care se obtine suma maxima.
Exemplu:
n=4
8 1 5 8
3 5 6 1
6 3 4 8
5 6 1 4
suma maxima este 26
si se obtine din valorile 8 6 8 4
Rezolvare

#399. [2012-12-05 - 23:02:32]
Se citeste o matrice patratica de ordin n formata din numere naturale.
Se calculeaza sume pornind de pe prima linie prin deplasari in vecinii de sub si din dreapta. Gasiti suma maxima care se poate calcula astfel si care sunt valorile din care se obtine suma maxima.
Exemplu:
n=4
7 1 5 8
3 5 6 1
6 3 4 8
5 6 1 4
suma maxima este 23
si se obtine din valorile 5 6 8 4
Rezolvare

#398. [2012-12-05 - 09:32:49]
Se dau n(n+1)/2 numere naturale aranjate intr-un triunghi format din elementele de sub si de pe diagonala unei matrici patratice de ordin n.
Se calculeaza sume pornind din elementul de pe prima linie prin deplasari in vecinii de sub si din dreapta. Gasiti suma maxima care se poate calcula astfel si care sunt valorile din care se obtine suma maxima.
Exemplu:
n=4
2
3 5
6 3 4
5 6 1 4
suma maxima este 17
si se obtine din valorile 2 3 6 6
Rezolvare

#202. [2010-03-02 - 09:38:33]
In fisierul m.in se afla pe prima linie un numar natural n cel mult 20000,iar pe liniile urmatoare o matrice patratica de dimensiune n care contine doar elemente 0 si 1.
Sa se determine cel mai mare patrat care contine doar valori 1. Se for afisa in fisierul text m.out urmatoarele valori separate prin spatiu: latura patratului, linia si coloana coltului stanga sus al patratului. Daca exista mai mult astfel de patrate se va afisa doar cel mai de sus.
Exemplu:
5
1 1 0 0 0
1 1 1 0 1
1 1 1 1 1
1 1 1 0 0
1 0 1 1 1
Se afiseaza 3 2 1
Rezolvare

#174. [2010-02-15 - 20:56:26]
O tabla de sah se citeste ca o matrice n*n in care pozitiile libere au valoarea 0, iar piesele sunt marcate prin valoarea 1.
Pe prima linie pe coloana js se afla un pion. Sa se determine drumul pe care poate ajunge pionul pe ultima linie luand un numar maxim de piese.
Pozitia initiala a pionului se considera libera.
Pionul aflat in pozitia i,j se poate deplasa astfel:
- in pozitia i+1,j daca e libera
- in pozitia i+1, j-1 daca e piesa in aceasta pozitie
- in pozitia i+1, j+1 daca e piesa in aceasta pozitie

Exemplu:
5 3
0 0 0 0 0
0 1 0 1 0
0 1 1 1 1
0 0 0 1 1
0 1 0 1 1

Drumul optim este:
1 3
2 2
3 3
4 4
5 5
Pe acest drum pionul ia 4 piese.
Rezolvare


29 mar 2024
Site-ul conține 884 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian