3379 - nkgraf

Cerința

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. 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ă.

Exemplu 1

Intrare

1
3 2 6

Iesire

15

Exemplu 2

Intrare

2
3 2 6

Iesire

1 3
2 1

Rezolvare

<syntaxhighlight lang="python" line> from itertools import permutations, combinations

def read_input():

   with open("nkgraf.in", "r") as file:
       cerinta = int(file.readline().strip())
       N, K, P = map(int, file.readline().strip().split())
   return cerinta, N, K, P

def write_output(output):

   with open("nkgraf.out", "w") as file:
       if isinstance(output, int):
           file.write(str(output) + "\n")
       else:
           for edge in output:
               file.write(" ".join(map(str, edge)) + "\n")

def generate_graphs(N, K):

   nodes = range(1, N + 1)
   possible_edges = list(permutations(nodes, 2))
   all_graphs = list(combinations(possible_edges, K))
   return sorted(all_graphs)

def main():

   cerinta, N, K, P = read_input()

   # Validări
   if not (2 <= N <= 30):
       raise ValueError("N trebuie să fie între 2 și 30")
   if not (1 <= P <= min(len(generate_graphs(N, K)), 1000000)):
       raise ValueError("P trebuie să fie între 1 și min(NR, 1.000.000)")

   all_graphs = generate_graphs(N, K)
   NR = len(all_graphs)

   if cerinta == 1:
       write_output(NR)
   elif cerinta == 2:
       graph = all_graphs[P - 1]
       write_output(graph)

if __name__ == "__main__":

   main()

</syntaxhighlight>