Se consideră un graf neorientat cu N noduri și N muchii în care fiecare nod are exact două muchii adiacente (fiecare nod are gradul 2).
Costurile muchiilor sunt numere prime, dar sunt necunoscute. Costul unui nod este dat de produsul costurilor muchiilor adiacente nodului respectiv. Nodurile sunt identificate prin numere cuprinse între 1 și N, iar costurile lor sunt cunoscute. Va trebui să determinați costurile muchiilor folosind datele furnizate de o bibliotecă externă. Biblioteca vă va pune la dipoziție rutine pentru:
Pentru a putea folosi biblioteca va trebui să includeți în programul dumneavoastră istrucțiunea uses graph; pentru limbajul Pascal și #include "graph.h" pentru limbajul C/C++. În continuare sunt prezentate sintaxele funcțiilor și procedurilor incluse în biblioteci:
procedure Init; void Init() - trebuie apelată la începutul programului și este folosită de către bibliotecă pentru inițializare; - întrerupe execuția programului dacă este apelată a doua oară. function GetNumberOfNodes:Integer; int GetNumberOfNodes() - returnează numărul nodurilor (și al muchiilor) din graf. function IsEdgeBetween(x,y:Integer):Boolean; int IsEdgeBetween(int x,int y) - returnează true (valoare nenulă) dacă există o muchie între nodurile x și y și false (0) dacă nu există o astfel de muchie; - întrerupe execuția programului dacă cel puțin una dintre valorile x și y nu reprezintă un nod al grafului. function CheckEdgeWeight(x,y,c:Integer):Boolean; int CheckEdgeWeight(int x,int y,int c) - returnează true (valoare nenulă) dacă muchia dintre nodurile x și y are costul c și false (0) dacă muchia are costul diferit de c; - întrerupe execuția programului dacă cel puțin una dintre valorile x și y nu reprezintă un nod al grafului, dacă muchia determinată de aceste noduri nu face parte din graf sau dacă a fost depășit numărul maxim admis de apeluri ale acestei funcții. function GetNodeWeight(x:Integer):Longint; long GetNodeWeight(int x) - returnează costul nodului x; - întrerupe execuția programului dacă x nu reprezintă un nod al grafului. function GetNumberOfCallsLeft:Integer; int GetNumberOfCallsLeft() - returnează un număr întreg care reprezintă numărul de apeluri ale funcției CheckEdgeWeight pe care le mai aveți la dispoziție. function Result(x,y,c:Integer):Boolean; int Result(int x,int y,int c) - acceptă ca rezultat faptul că muchia dintre nodurile x și y are costul c; - întrerupe execuția programului dacă:
Programul vostru nu va citi datele din nici un fișier de intrare și nu va scrie date în nici un fișier de ieșire.
3 <= N <= 10000.
Subprogram apelat Valoare returnată
Costurile muchiilor sunt numere prime cuprinse între 2 și 29989. Init - GetNumberOfNodes 4 IsEdgeBetween(1,2) true (1) IsEdgeBetween(1,3) false (0) IsEdgeBetween(1,4) true (1) IsEdgeBetween(2,3) true (1) IsEdgeBetween(2,4) false (0) IsEdgeBetween(3,4) true (1) GetNumberOfCallsLeft 2 GetNodeWeight(1) 14 GetNodeWeight(2) 6 GetNodeWeight(3) 15 GetNodeWeight(4) 35 CheckEdgeWeight(1,2,7) false (0) CheckEdgeWeight(1,2,2) true (1) Result(1,2,2) - Result(2,3,3) - Result(3,4,5) - Result(4,1,7) - |