Confederația Galactică deține controlul asupra a N planete între care există un număr total de M rute comerciale directe. Planetele vor fi identificate prin numere cuprinse între 1 și N, iar rutele comerciale prin numere cuprinse între 1 și M. Fiecare rută comercială directă este folosită pentru transporturi între perechi distincte de planete. Un circuit comercial este format din k planete distincte a1, a2, ..., ak astfel încât există o rută comercială directă între planetele ai și ai+1 pentru i cuprins între 1 și k-1 și există o rută comercială directă între planetele ak și a1. Două circuite comerciale sunt distincte dacă și numai dacă există cel puțin o rută comercială care apare în unul dintre ele și nu apare în celălalt. Pentru fiecare rută comercială, va trebui să stabiliți din câte circuite comerciale distincte face parte.
Fișierele de intrare sunt deschise și pot fi descărcate folosind link-urile de pe pagina dedicată problemei. Numele acestora au forma GALAXYXX.IN, unde XX ia valori între 01 și 20 și reprezintă numărul testului.
Fiecare dintre cele 20 fișiere de intrare conține pe prima linie numărul N al planetelor și numărul M al rutelor comerciale directe. Următoarele M linii vor conține câte două numere întregi distincte cuprinse între 1 și N care sunt numerele de identificare ale planetelor legate între ele prin ruta comercială corespunzătoare liniei.
Pentru această problemă nu va trebui să trimiteți un program care să o rezolve, ci doar cele 20 de fișiere de ieșire corecte. Acestea vor fi denumite GALAXYXX.OUT, unde XX ia valori între 01 și 20 și reprezintă numărul testului.
Prima linie a fișierului de ieșire va conține textul GALAXY - TEST #XX, unde XX reprezintă numărul testului. Următoarele M linii vor conține câte un număr întreg care reprezintă numărul de circuite comerciale distincte din care face ruta corespunzătoare liniei. Informațiile referitoare la rute vor apărea în ordinea în care sunt descrise rutele în fișierul de intrare corespunzător.
Vom considera că acest exemplu reprezintă testul 00.
Pentru fiecare fișier de ieșire corect veți obține un anumit număr de puncte. Punctajul maxim care poate fi obținut (dacă toate cele 20 de fișiere de ieșire sunt corecte) este de 100 de punte. Pentru primele patru teste (01 - 04) se vor acorda câte 3 puncte, pentru următoarele patru (05 - 08) câte 4 puncte, pentru următoarele patru (09 - 12) câte 5 puncte, pentru următoarele patru (13 - 16) câte 6 puncte, iar pentru ultimele patru (17 - 20) câte 7 puncte.GALAXY00.IN 4 5 1 2 1 3 2 3 2 4 3 4 GALAXY00.OUT GALAXY - TEST #00 2 2 2 2 2
Arhiva pe care o veți trimite se va numi YYYYYR15.ZIP, YYYYYR15.RAR sau YYYYYR15.ACE (în funcție de programul de arhivare pe care îl folosiți), unde YYYYY este codul dumneavoastră de identificare (ID). Ea nu va conține fișiere batch (YYYYYR15.BAT) sau fișiere sursă (YYYYYR15.PAS, YYYYYR15.CPP sau YYYYYR15.C). În arhivă se vor afla cele 20 de fișiere de ieșire corecte, denumirea lor fiind GALAXYXX.OUT, unde XX reprezintă numărul testului (cuprins între 01 și 20). |