Rezolvare PBinfo #3379

Fie N, K, P trei numere naturale nenule. Vom considera toate grafurile orientate care au N vârfuri şi K arce, reprezentate prin lista arcelor lor ordonate lexicografic.
Vom ordona apoi grafurile lexicografic şi le vom numerota începând cu 1.

Cerința

Scrieţi un program care, cunoscând N, K şi P, rezolvă următoarele două cerinţe:
1. determină NR, numărul de grafuri orientate cu N vârfuri şi K arce;
2. determină graful orientat cu N vârfuri şi K arce având numărul de ordine P.

Date de intrare

Fișierul de intrare nkgraf.in conţine pe prima linie cerinţa care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află trei numere naturale separate prin câte-un spaţiu N K P, având semnificaţia din enunţ.

Date de ieșire

Dacă cerinţa este 1, fişierul de ieşire nkgraf.out va conţine o singură linie pe care va fi scris NR, numărul de grafuri orientate cu N vârfuri şi K arce.
Dacă cerinţa este 2, fişierul de ieşire nkgraf.out va conţine K linii pe care vor fi scrise în ordine lexicografică cele K arce ale grafului având numărul de ordine P, câte un arc pe o linie; pentru fiecare arc vor fi scrise două vârfuri separate printr-un spaţiu, reprezentând extremitatea iniţială şi respectiv extremitatea finală a arcului.

Restricții și precizări

• 2 ≤ N ≤ 30
• 1 ≤ P ≤ min {NR,1.000.000}
• Orice arc din graf a avea extremitatea iniţială diferită de extremitatea finală.

Exemplul 1:

nkgraf.in

1
3 2 6

nkgraf.out

15

Exemplul 2:

nkgraf.in

2
3 2 6

nkgraf.out

1 3
2 1

Explicație

Există 15 grafuri cu 3 vârfuri şi două arce. În ordine lexicografică acestea sunt:
Graf 1: (1,2), (1,3)
Graf 2: (1,2), (2,1)
Graf 3: (1,2), (2,3)
Graf 4: (1,2), (3,1)
Graf 5: (1,2), (3,2)
Graf 6: (1,3), (2,1)
Graf 7: (1,3), (2,3)
Graf 8: (1,3), (3,1)
Graf 9: (1,3), (3,2)
Graf 10: (2,1), (2,3)
Graf 11: (2,1), (3,1)
Graf 12: (2,1), (3,2)
Graf 13: (2,3), (3,1)
Graf 14: (2,3), (3,2)
Graf 15: (3,1), (3,2)