Editing 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<br>
3 2 6
;Iesire
15
== Exemplu 2 ==
;Intrare
2<br>
3 2 6
;Iesire
1 3<br>
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>