Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | divisorgraph.in, divisorgraph.out | Sursă | Algoritmiada 2014, Runda Finala |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Divisorgraph
Fie un număr natural N. Se numeşte DivisorGraph al numărului N, un graf orientat cu NrDivizori(N) noduri obţinut după cum urmează:
1. Fiecărui divizor al lui N i se asociază un nod unic. De-asemenea, fiecare nod are asociat exact un divizor al lui N. Cu alte cuvinte, există o bijecţie între divizorii lui N şi nodurile grafului.
2. Pentru orice pereche (A, B) de divizori ai lui N care respectă A > B şi pentru care B îl divide pe A, se adaugă un arc orientat de la nodul asociat lui A către nodul asociat lui B.
Dându-se un graf orientat G, care se garantează că este DivisorGraph al unui număr natural, se cere cel mai mic număr care produce un DivisorGraph izomorf cu G.
Date de intrare
Fişierul de intrare divisorgraph.in ...
Date de ieşire
În fişierul de ieşire divisorgraph.out ...
Restricţii
- 1 ≤ V ≤ 5.000
- 1 ≤ E $le; 500.000
- Doua grafuri A şi B sunt izomorfe dacă şi numai dacă există o bijecţie între ele, f, astfel încât arcul f(x) -> f(y) apare în B dacă şi numai dacă arcul x -> y apare în A
Exemplu
| divisorgraph.in | divisorgraph.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
