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