Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Digrafuri

Rândul 1

Într-o fabrică există N secţii numerotate de la 1 la N. Secţia 1 este secţia de plecare, iar secţia N este cea unde ajung produsele finite. O secţie nu poate furniza produsul intermediar în care este specializată până când nu-i sosesc toate „ingredientele” de la secţiile de care ea depinde. Se cunosc pentru anumite perechi de secţii (i, j) timpii necesari transportului produselor pe drumul de la secţia i la secţia j.
Fişierul fabrica.in conţine pe prima linie numărul N al secţiilor şi numărul M al perechilor de secţii între care se cunoaşte timpul necesar transportului, iar pe următoarele M linii se găsesc câte 3 numere naturale i j t cu semnificaţia: drumul de la secţia i la secţia j este parcurs în t minute.
Fişierul fabrica.out va afişa timpul minim necesar pentru fabricarea produsului finit din momentul din care în secţia de plecare începe să funcţioneze.

Exemplu:

fabrica.in

fabrica.out

Explicaţii

5 5
1 2 5
2 4 3
3 4 10
1 3 1
4 5 1

12

Sunt 5 secţii şi se cunosc 5 timpi necesari transportului produselor de la o secţie la alta: timpul necesar de la secţia 1 la secţia 2 este 5 minute, timpul de la secţia 2 la 4 este 3 minute etc.
Timpul minim necesar fabricării produsului finit este 12.

 

Rândul 2

Gigel, elev nu prea conştiincios, are de rezolvat N exerciţii la matematică. Pentru fiecare exerciţiu i, Gigel poate estima timpul ti necesar rezolvării. Ordinea rezolvării exerciţiilor nu contează, dar există mai multe perechi de exerciţii (i, j) cu proprietatea că pentru a putea fi rezolvat exerciţiul j trebuie mai întâi rezolvat exerciţiul i. Pentru că nu doreşte să rezolve toate exerciţiile, dar doreşte (pentru salvarea aparenţelor!) să rezolve neapărat exerciţiile 1 şi N, să se determine timpul minim necesar pentru rezolvarea unor exerciţii astfel încât să rezolve obligatoriu exerciţiile 1 şi N.
Fişierul exerc.in conţine pe prima linie numărul natural N reprezentând numărul de exerciţii. Pe linia a doua se găsesc N numere naturale strict pozitive t1 t2 ... tN reprezentând timpii necesari rezolvării celor N exerciţii. Pe linia a treia se găseşte un număr natural M, iar pe următoarele M linii se află gâte 2 numere naturale i j cu semnificaţia: exerciţiul i trebuie rezolvat înaintea exerciţiului j.
Fişierul exerc.out conţine un singur număr natural K reprezentând timpul minim total necesar rezolvării unora din cele N exerciţii, obligatoriu fiind rezolvate şi exerciţiile 1 şi N.

Exemplu:

exerc.in

exerc.out

Explicaţii

6
5 7 2 3 6 1
8
1 2
5 6
4 6
3 5
2 3
2 4
1 3
3 4

11

Sunt 6 exerciţii. Exerciţiul 1 necesită 5 minute, al doilea 7 minute, al treilea 2 minute etc.
Sunt 7 relaţii i j cu semnificaţia: exerciţiul i trebuie rezolvat înaintea exerciţiului j. Relaţia 1 2 înseamnă că întâi trebuie rezolvat exerciţiul 1, apoi exerciţiul 2.
Timpul minim total necesar este 11: se rezolvă în ordine exerciţiile 1, 3, 4, 6, cu timpii 5+2+3+1.


Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =