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

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()