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)

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)

Grafuri orientate

#828. [2017-04-05 - 09:49:18]
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Se numeste arc inutil un arc cu proprietatea ca are extremitatile in componente tare conexe diferite. Afisati numarul de arce inutile si care sunt acestea.
Exemplu:
graf.in
8 11
1 3
3 5
5 7
7 1
2 6
6 8
8 2
1 4
4 6
4 8
4 2
graf.out
4
1 4
4 2
4 6
4 8

#827. [2017-04-05 - 09:20:50]
Se da un graf orientat tare conex cu n varfuri si m arce etichetate costuri pozitive. Calculati si afisati distanta maxima dintre doua varfuri ale grafului. Distanta de la i la j este egala cu suma costurilor arcelor ce formeaza drumul de cost minim de la i la j. Afisati varfurile aflate la distanta maxima unul de celalalt.
Exemplu:
graf.in
8 14
1 2 3
1 3 6
2 3 3
3 4 6
4 5 8
5 6 2
6 7 1
8 7 7
7 8 5
8 1 4
6 3 3
6 2 2
6 4 2
7 3 1
graf.out
29
2 1

#826. [2017-04-05 - 09:00:14]
Se da un graf orientat tare conex cu n varfuri si m arce prin lista arcelor. Se numeste varf central un varf cu proprietatea ca suma distantelor de la el la toate celelalte varfuri este minim. Distanta de la i la j este egala cu lungimea celui mai scurt drum de la i la j. Afisati varfurile centrale ale grafului. Se va folosi algoritmul Roy-Floyd pentru arce de cost 1.
Exemplu:
graf.in
8 13
1 2
1 3
2 3
3 4
4 5
5 6
6 7
8 7
7 8
8 1
6 3
6 2
6 4
graf.out
6

#825. [2017-04-05 - 08:42:50]
Se da un graf orientat tare conex cu n varfuri si m arce prin lista arcelor. Se numeste varf central un varf cu proprietatea ca suma distantelor de la el la toate celelalte varfuri este minim. Distanta de la i la j este egala cu lungimea celui mai scurt drum de la i la j. Afisati varfurile centrale ale grafului. Se va folosi un algoritm de tip breadth-first.
Exemplu:
graf.in
8 13
1 2
1 3
2 3
3 4
4 5
5 6
6 7
8 7
7 8
8 1
6 3
6 2
6 4
graf.out
6

#756. [2015-11-11 - 09:36:18]
Cuplaj maxim in graf bipartit (cu flux maxim). Vezi http://infoarena.ro/problema/cuplaj

#755. [2015-11-11 - 09:31:00]
Flux maxim intr-o retea de transport (Algoritmul Edmonds-Karp).

#475. [2013-05-22 - 10:25:49]
Se da un graf orientat cu n varfuri si m arce avand arcele etichetate cu costuri numere naturale.
Se citesc apoi doua varfuri x si y. Afisati drumul de cost minim de la varful x la varful x trecand prin varful y, precum si costul acestui drum.
Exemplu:
date.in
12 21 (n,m)
1 2 20 (arcele si costurile)
1 3 35
1 7 20
2 4 30
3 4 40
3 6 40
3 8 80
4 5 25
5 6 5
6 8 30
6 9 10
7 8 15
7 11 100
8 9 40
8 10 30
8 11 35
9 10 30
10 12 25
11 12 10
10 5 15
5 1 10
1 10 (x,y)
date.out
1 7 8 10 5 1
90

#471. [2013-05-17 - 09:10:45]
Se considera un graf turneu cu n varfuri avand arc (i,j) intre oricare doua varfuri i,j cu proprietatea ca i este mai mic decat j.
Afisati toate drumurile elementare de la un varf x la un un varf y, x si y citite, avand proprietatea ca x este mai mic decat y.
Exemplu:
date.in
9 3 7 (n, x, y)
date.out
3 4 5 6 7
3 4 5 7
3 4 6 7
3 4 7
3 5 6 7
3 5 7
3 6 7
3 7

#451. [2013-04-19 - 11:51:26]
Se da un graf orientat cu n v�rfuri si m arce prin lista arcelor si un varf k.
Calculati cate varfuri are componenta tare conexa in care se afla varful k.
Exemplu:
date.in
7 10 (n,m)
1 2
1 3
2 6
3 6
3 2
6 1
3 4
4 5
4 7
7 4
3 (k)
date.out
4

#450. [2013-04-19 - 11:49:34]
Se da un graf orientat cu n v�rfuri si m arce prin lista arcelor si doua varfuri distincte k si l.
Determinati daca varfurile k si l se afla in aceeasi componenta tare conexa a grafului.
Exemplu:
7 10 (n,m)
1 2
1 3
2 6
3 6
3 2
6 1
3 4
4 5
4 7
7 4
3 4 -> nu
3 6 -> da

#449. [2013-04-19 - 11:46:26]
Se da un graf orientat cu n v�rfuri si m arce prin lista arcelor si un varf k.
Afisati varfurile din componenta tare conexa in care se afla varful k.
Exemplu:
date.in
7 10 (n,m)
1 2
1 3
2 6
3 6
3 2
6 1
3 4
4 5
4 7
7 4
3 (k)
date.out
1 2 3 6

#445. [2013-03-29 - 09:40:22]
Harta unui oras este impartita in n intersectii si m strazi cu sens unic intre intersectii, fiecare strada avand o lungime. Pentru doua intersectii i si j poate exista atat strada de la i la j, cat si de la j la i.
Intr-o intersectie x se gaseste Julieta si intr-o intersectie y se gaseste Romeo. Cei doi se pot deplasa pe strazi in sensurile de parcurgere ale acestora.
Determinati intersectia in care trebuie sa se intalneasca cei doi astfel incat sa parcurga in total o distanta minima.
Pentru solutia obtinuta afisati intersectia, distanta parcursa de Julieta, distanta parcursa de Romeo si traseul parcurs de fiecate dintre ei.
Datele de intrare asigura ca cei doi se pot intalni.
Exemplu:
date.in
12 19 (n,m)
1 2 20 (intersectie 1, intersectie 2, lungime strada)
1 3 35
1 7 20
2 4 30
3 4 40
3 6 40
3 8 80
4 5 25
5 6 5
6 8 30
6 9 10
7 8 15
7 11 100
8 9 40
8 10 30
8 11 35
9 10 30
10 12 25
11 12 10
1 6 (Julieta, Romeo)
date.out
Intersectia: 8
Julieta merge: 35
Romeo merge: 30
Traseul Julietei: 1 7 8
Traseul lui Romeo: 6 8

#443. [2013-03-28 - 12:51:49]
Intr-o fabrica exista n sectii numerotate de la 1 la n si impartite in 3 categorii:
-sectii de intrare, adica sectii prin care intra in fabrica materii prime
-sectii intermediare, care primesc produse intermediare de la alte sectii, le prelucreaza si le transmit la randul lor altor sectii
-sectia numerotata cu n care este o sectie de finalizare a productiei
Pentru fiecare sectie dintre cele n se cunosc urmatoarele informatii:
- durata necesara pentru prelucrarea in sectia respectiva
- numarul sectiilor si sectiile care furnizeaza produse intermediare sectiei curente
Stiind ca durata transportului produselor intermediare intre sectii este neglijabila, ca in fabrica nu se formeaza circuite de productie si ca O sectie poate sa-si inceapa activitatea doar dupa sect care furnizeaza
materii le-au furnizat.
Calculati urmatoarele:
- timpul necesar pt fabricarea produsului finit
- pt fiecare sectie timpul cel mai devreme ca sa poata incepe productia si timpul cel mai tarziu in care poate incepe productia astfel incat durata totala a productiei sa nu fie afectata.
Oservatii:
- sectiile fabriici pot lucra simultan
- sectiile de intrare pornesc cel mai devremea la momentul 0.
Indicatii:
- duratele din varfuri se se muta pe arce
- se construieste matrice a costurilor (duratelor)
- se aplica algoritmul Roy-Floyd pentru drum de cost maxim
- durata productiei este maximul de pe ultima linia adunat cu durata de prelucrare din sectia n
- cel mai repede o sectie poate incepe productia dupa ce au ajuns in ea produsele din sectiile de care depinde, adica maximul de pe coloana
- cel mai tarziu o sectie poate incepe productia astfel incat durata productiie de la ea la ultima sectie sa nu fie mai mare decat durata de productie a celorlalte sectii, si se obtine prin diferenta de pe ultima coloana dintre maxim si fiecare element (durata corespunzatoare fiecarei sectii).
Exemplu:
date.in
12 (n)
3 1 8 3 5 3 6 7 1 7 9 6 (costurile)
0 (sectia 1 nu depinde de alta)
2 1 10 (sectia 2 depinde de 2 sectii, si anume de 1 si 10)
3 2 4 9
2 10 11
1 3
2 3 7
2 4 9
2 3 7
1 11
0
0
3 5 6 8
date.out
matricea costurilor maxime
0 3 4 # 12 12 # 12 # # # 19
# 0 1 # 9 9 # 9 # # # 16
# # 0 # 8 8 # 8 # # # 15
# # 3 0 11 11 3 11 # # # 18
# # # # 0 # # # # # # 5
# # # # # 0 # # # # # 3
# # # # # 6 0 6 # # # 13
# # # # # # # 0 # # # 7
# # 1 # 9 9 1 9 0 # # 16
# 7 10 7 18 18 10 18 # 0 # 25
# # 12 9 20 20 12 20 9 # 0 27
# # # # # # # # # # # 0
33 (durata productiei)
0 8 (cel mai devreme, cel mai tarziu)
7 11
12 12
9 9
20 22
20 24
12 14
20 20
9 11
0 2
0 0
27 27

#442. [2013-03-21 - 08:28:49]
Se citeste un graf orientat cu n noduri si m arce dat prin lista arcelor.
- Construiti matricea drumurilor folosind algoritmul Roy-Warshall.
- Folosind matricea drumurilor afisati componentele tare conexe.
Exemplu:
date.in
7 10
1 2
1 3
2 6
3 6
3 2
6 1
3 4
4 5
4 7
7 4
date.out
1 2 3 6
4 7
5

#440. [2013-03-18 - 23:09:57]
Se citeste un graf orientat cu n noduri si m arce dat prin vectorul arcelor. Sa se calculeze lungimea minima a drumului dintre oricare doua noduri din graf.
Se va folosi parcurgerea in latime.
Exemplu:
date.in
7 13
1 2
1 3
2 3
2 6
2 5
3 1
3 5
3 6
4 5
4 7
5 7
7 6
6 4
date.out
0 1 1 3 2 2 3
2 0 1 2 1 1 2
1 2 0 2 1 1 2
# # # 0 1 2 1
# # # 3 0 2 1
# # # 1 2 0 2
# # # 2 3 1 0
(# semnaleaza faptul ca nu exista drum intre varfurile corespunzatoare)

#439. [2013-03-18 - 23:03:29]
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Se citeste apoi un numar k si o submultime X cu k varfuri din multimea varfurilor grafului, notata cu V. Afisati arcele din graful citit care au proprietatea ca au o extremitate in multimea X si cealalta in multimea V-X.
Exemplu:
6 7 (n,m)
1 2
2 1
3 4
1 5
4 5
5 6
6 1
3 (k)
1 2 3 (multimea x)
Arcele cerute sunt:
3 4
1 5
6 1

#438. [2013-03-13 - 22:40:16]
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Afisati circuitele hamiltoniene ale grafului.
Exemplu:
n=5 m=10
arcele:
1 2
2 3
3 4
4 5
5 1
1 3
3 5
5 2
2 4
4 1
circuitele hamiltoniene sunt:
1 2 3 4 5 1
1 3 5 2 4 1
2 3 4 5 1 2
2 4 1 3 5 2
3 4 5 1 2 3
3 5 2 4 1 3
4 1 3 5 2 4
4 5 1 2 3 4
5 1 2 3 4 5
5 2 4 1 3 5

#437. [2013-03-13 - 22:34:49]
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Stiind ca graful nu are varfuri izolate, determinati daca este eulerian.
Exemple:
n=5 m=4
arcele:
1 2
2 3
3 4
4 5
nu este eulerian
n=5 m=10
arcele:
1 2
2 3
3 4
4 5
5 1
1 3
3 5
5 2
2 4
4 1
este eulerian

#436. [2013-03-13 - 22:26:28]
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Determinati daca este hamiltonian.
Exemple:
n=5 m=4
arcele:
1 2
2 3
3 4
4 5
nu este hamiltonian
n=5 m=10
arcele:
1 2
2 3
3 4
4 5
5 1
1 3
3 5
5 2
2 4
4 1
este hamiltonian

#435. [2013-03-07 - 08:49:12]
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Determinati numarul minim de culori cu care se pot colora varfurile grafului astfel incat oricare doua varfuri adiacente sa aiba culori diferite.
Numerotand apoi culorile necesare, realizati o colorare a varfurilor grafului dat si precizati pentru fiecare varf culoare cu care il colorati.
De asemenea, pentru fiecare culoare afisati nodurile care se coloreaza cu ea.
Exemplu:
date.in
6 7
1 2
2 1
3 4
1 5
4 5
5 6
6 4
date.out
numarul minim de culori: 3
colorarea nodurilor:
1: 1
2: 2
3: 1
4: 3
5: 2
6: 1
pe culori:
culoarea 1: 1 3 6
culoarea 2: 2 5
culoarea 3: 4

#434. [2013-03-07 - 08:24:07]
Se citeste un graf orientat cu n noduri si m arce dat prin vectorul arcelor. Sa se afiseze varfurile care compun cea mai mare componenta tare conexa a grafului citit (cea care are cele mai multe varfuri).
Exemplu:
date.in
6 7
1 2
2 1
3 4
1 5
4 5
5 6
6 4
date.out
4 5 6

#431. [2013-02-28 - 12:58:30]
Se citeste un graf orientat cu n varfuri si m arce prin lista arcelor. Se da numar natural k mai mic decat n si k varfuri ale grafului.
Afisati toate drumurile elementare care au ca extremitate initiala varful 1, ca extremitate finala varful n si care trec prin cele k varfuri citite in ordinea in care au fost citite.
Exemplu:
date.in
7 13 3 (n,m,k)
1 2
1 3
2 3
2 6
2 5
3 1
3 5
3 6
4 5
4 7
5 7
7 6
6 4
2 6 4 (cele k varfuri)
date.out
1 2 3 6 4 5 7
1 2 3 6 4 7
1 2 6 4 5 7
1 2 6 4 7

#430. [2013-02-24 - 19:20:26]
La un turneu de tenis participa n jucatori cu numerele de ordine de la 1 la n. Fiecare dintre ei joaca cu toti ceilati cate o partida. Fiecare dintre partide este data ca o pereche de jucatori (i,j) cu semnificatia ca jucatorul i l-a invins pe jucatorul j.
Afisati primii 3 jucatori in ordine descrescatoare a numarului de victorii din turneu.
Exemplu:
date.in
5
1 2 *(cu semnificatia ca jucatorul 1 l-a invins pe jucatorul 2)
3 2
3 4
1 4
5 1
3 5
5 4
3 1
5 2
2 4
date.out
3 4 *(cu semnificatia ca jucatorul 3 are 4 victorii)
5 3
1 2

#429. [2013-02-24 - 17:37:12]
Se citeste un graf orientat cu n varfuri si m arce prin lista arcelor. Se citeste apoi un numar natural k mai mic decat n.
a) Afisati toate subgrafurile cu k varfuri ale subgrafului dat.
b) Afisati numarul maxim de arce ale unui subgraf cu k varfuri ale grafului dat.
c) Afisati cate dintre subgrafurile cu k varfuri ale subgrafului dat sunt complete.
Exemplu:
date.in
5 9
1 2
1 3
3 4
4 1
2 5
5 3
3 2
4 2
2 1
4
date.out
varfuri: 1 2 3 4
arce: (1,2) (1,3) (2,1) (3,2) (3,4) (4,1) (4,2)
varfuri: 1 2 3 5
arce: (1,2) (1,3) (2,1) (2,5) (3,2) (5,3)
varfuri: 1 2 4 5
arce: (1,2) (2,1) (2,5) (4,1) (4,2)
varfuri: 1 3 4 5
arce: (1,3) (3,4) (4,1) (5,3)
varfuri: 2 3 4 5
arce: (2,5) (3,2) (3,4) (4,2) (5,3)
maxim de arce: 7
numar de subgrafuri complete: 1

#428. [2013-02-24 - 17:37:04]
Transformati un graf orientat complet in graf turneu. Graful complet se da cu n varfuri si m arce prin lista arcelor. Graful turneu se va afisa ca matrice de adiacenta.
Exemplu:
date.in
3 5
1 2
1 3
2 1
2 3
3 1
date.out:
0 1 1
0 0 1
0 0 0

#404. [2012-12-06 - 15:05:03]
Bellman-Ford cu coada.
date.in
6 10
1 2 2
1 3 1
1 6 9
2 5 3
2 4 3
3 4 3
3 5 7
4 6 2
5 4 4
6 3 3
2
date.out
- 0 8 3 3 5
2->1:-
2->2:-
2->3:2 4 6 3
2->4:2 4
2->5:2 5
2->6:2 4 6

#43. [2009-03-16 - 19:14:19]
Intr-o fabrica exista n sectii numerotate de la 1 la n. Sectia 1 este sectia de intrare a materiilor prime, iar sectia n cea de livrare a produselor finite. Celelalte n-2 sectii sunt sectii de productie care primesc produse intermediare de la alte sectii si livreaza la randul lor produse intermediare altora. O sectie nu poate livra un produs decat dupa ce ii sosesc produsele intermediare de la sectiile de care depinde ea.
Se cunosc timpii de productie pentru fiecare din cele n sectii, sectia n avand obligatoriu timpul de productie egal cu 0. Se cunosc cele m perechi de sectii (i,j) cu semnificatia ca sectia i furnizeaza produse sectiei j si, de asemea, se cunoaste pentru fiecare astfel de pereche durata transportului intre cele 2 sectii. Se cere sa se determine durata productiei, adica timpul scurs de la inceperea functionarii sectiei 1 si pana la sosirea produselor la sectia n.

#42. [2009-03-16 - 18:35:02]
Intr-o fabrica exista n sectii numerotate de la 1 la n. Sectia 1 este sectia de intrare a materiilor prime, iar sectia n cea de livrare a produselor finite. Celelalte n-2 sectii sunt sectii de productie care primesc produse intermediare de la alte sectii si livreaza la randul lor produse intermediare altora. O sectie nu poate livra un produs decat dupa ce ii sosesc produsele intermediare de la sectiile de care depinde ea. Se cunosc cele m perechi de sectii (i,j) cu semnificatia ca sectia i furnizeaza produse sectiei j si, de asemea, se cunoaste pentru fiecare astfel de pereche durata transportului intre cele 2 sectii. Se cere sa se determine durata productiei, adica timpul scurs de la inceperea functionarii sectiei 1 si pana la sosirea produselor la sectia n. (se considera ca timpul de prelucrare in fiecare sectie este 0)

#40. [2009-03-15 - 21:58:28]
Se citeste un graf orientat cu n varfuri si m arce, dat prin vestorul arcelor. Se citeste apoi un numar natural k mai mic decat n. Sa se afiseze nodurile care se afla la distanta k se nodul 1. Distanta de la un nod x la un nod y este egala cu numarul de arce din care este compus cel mai scurt drum de la nodul x la nodul y.
Ex: Pentru graful din imaginea alaturata, daca se citeste k=2 se afiseaza varfurile 2, 3 si 6.

#38. [2009-03-15 - 21:30:54]
Se citeste un graf orientat cu n varfuri si m arce, dat prin vectorul arcelor. Sa se afiseze varfurile care au gradul interior egal cu cel exterior.
Ex: Pentru graful din figura alaturata se vor afisa nodurile 2 si 3.

#35. [2009-03-09 - 18:49:20]
Se da un graf orientat cu n varfuri si m arce, citit prin vectorul arcelor. Sa se afiseze toate circuitele euleriene pe care le are graful.

#23. [2009-03-08 - 00:09:16]
Se citeste un graf orientat cu n noduri si m arce dat prin vectorul arcelor. Sa se determine daca graful contine circuite.

#21. [2009-03-08 - 00:02:26]
Se citesc 2 grafuri orientate, unul cu n noduri si m arce, iar celalalt cu k varfuri si l arce, ambele date prin vectorul arcelor. Sa se determine daca al doilea graf este subgraf al primului.

#20. [2009-03-07 - 23:45:58]
Se citeste un graf orientat cu n noduri si m arce dat prin vectorul arcelor. Sa se afiseze componentele tare conexe ale grafului.
Ex: Componentele tare conexe ale grafului alaturat sunt:
1 2 5
3 4 6

#11. [2009-03-07 - 21:47:55]
Drumuri de lungime minima intre oricare 2 noduri - algoritmul Roy-Floyd
Se citeste un graf orientat cu n noduri si m arce dat prin vectorul arcelor. Sa se calculeze lungimea minima a drumului dintre oricare doua noduri din graf.
Ex: Pentru graful alaturat matricea lungimilor minime este:
0 2 = = 1 =
1 0 = = 2 =
3 3 0 2 2 1
1 3 1 0 2 2
2 1 = = 0 =
2 2 2 1 1 0
(= reprezinta faptul ca nu exista drum)

#10. [2009-03-07 - 21:45:43]
Drumuri de cost minim intre oricare 2 noduri - algoritmul Roy-Floyd
Se citeste un graf orientat cu n noduri si m arce, etichetate cu valori naturale. Sa se calculeze costul minim al drumului dintre oricare doua noduri din graf.

#8. [2009-03-07 - 21:33:19]
Matricea drumurilor - algoritmul Roy-Warshall
Se citeste un graf orientat cu n noduri si m arce, dat prin vectorul arcelor. Sa se construiasca o matricea existentei drumurilor (a[i][j] este 1 daca exista drum de la i la j si 0 in caz contrar).
Ex: Pentru graful alaturat matricea existentei drumurilor este:
1 1 0 0 1 0
1 1 0 0 1 0
1 1 1 1 1 1
1 1 1 1 1 1
1 1 0 0 1 0
1 1 1 1 1 1

#7. [2009-03-07 - 21:26:01]
Drumuri de cost minim de la un nod la toate celelalte - algoritmul lui Dijkstra
Se citeste un graf orientat cu n noduri si m arce, etichetate cu valori naturale. Sa se calculeze costurile minime ale dumurilor de la un nod citit la toate celelalte. Sa se afiseze drumurile pentru care s-au obtinut costurile minime.

21 nov 2024

Site-ul conține 884 de probleme rezolvate

Copyright © 2009-2018 Muresan Vasile Ciprian