| Fișierul intrare/ieșire | drumuri.in, drumuri.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Victor Manz | Adăugată de |
Victor Manz
•
vmanz
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 512 KB |
| Scorul tău | N/A | Dificultate |
  2
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Drumuri
Care este numărul maxim de drumuri optime (drumuri cu număr minim de arce) care pot exista între două vârfuri ale unui graf orientat cu N vârfuri?
Date de intrare
Fișierul de intrare drumuri.in conține un singur număr natural N.
Date de ieșire
În fișierul de ieșire drumuri.out se va scrie un singur număr D reprezentând restul la împărțirea cu 9001 al numărului maxim de drumuri optime care pot exista între două vârfuri ale unui graf orientat cu N vârfuri.
Restricții
- 2 ≤ N ≤ 1018
Exemplu
| drumuri.in | drumuri.out |
|---|---|
| 6 |
4 |
Explicație
Fie graful orientat G cu vârfurile {1, 2, 3, 4, 5, 6} și arcele {(1,2), (1,3), (1,4), (1,5), (2,6), (3,6), (4,6), (5,6)}. Între vârfurile 1 și 6 există 4 drumuri optime (fiecare dintre acestea format din câte 2 arce): (1, 2, 6), (1, 3, 6), (1, 4, 6), (1, 5, 6). Acesta este numărul maxim de drumuri optime care pot exista între două vârfuri ale unui graf orientat cu 6 vârfuri.
