Benzar Ioan: Pagină nouă: == 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...

2024-06-03T19:24:28Z

Pagină nouă: == 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...

New page

== 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>

3379 - nkgraf - Revision history