# PBinfo #3379 – nkgraf – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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.

Cerința
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ă.

Exemplul 1:
nkgraf.in

1
3 2 6
nkgraf.out

15
Exemplul 2:
nkgraf.in

2
3 2 6
nkgraf.out

1 3
2 1
Explicație
Există 15 grafuri cu 3 vârfuri şi două arce. În ordine lexicografică acestea sunt:
Graf 1: (1,2), (1,3)
Graf 2: (1,2), (2,1)
Graf 3: (1,2), (2,3)
Graf 4: (1,2), (3,1)
Graf 5: (1,2), (3,2)
Graf 6: (1,3), (2,1)
Graf 7: (1,3), (2,3)
Graf 8: (1,3), (3,1)
Graf 9: (1,3), (3,2)
Graf 10: (2,1), (2,3)
Graf 11: (2,1), (3,1)
Graf 12: (2,1), (3,2)
Graf 13: (2,3), (3,1)
Graf 14: (2,3), (3,2)
Graf 15: (3,1), (3,2)

## Cod sursă C++

```cpp
//Em. Cerchez 100
#include <fstream>
#define LGMAX 300
#define NMAX 900
using namespace std;
ifstream fin("nkgraf.in");
ofstream fout("nkgraf.out");
typedef char NrMare[LGMAX];
struct arc {int x, y;};
void Afisare(NrMare x, int lgx);
void Suma(NrMare x, int lgx, NrMare y, int lgy, NrMare z, int& lgz);
void Zero(NrMare x, int st, int dr);
void combinari();
void arce();
void genereaza();
void afiseaza_sol();
int N, K, P, cerinta, n, lp, lc;
NrMare C[2][NMAX];
int lg[2][NMAX];
int sol[NMAX*NMAX];
arc a[NMAX*NMAX];
int main()
{
 fin>>cerinta>>N>>K>>P;
 n=N*(N-1);
 if (cerinta==1)
    {
     combinari();
     Afisare(C[lp][K],lg[lp][K]);
    }
    else
    {arce();
     genereaza();
     afiseaza_sol();
    }
 fout.close();
 return 0;
}
void Afisare(NrMare x, int lgx)
{int i;
  for (i=lgx-1; i>=0; i--) fout<<(int)x[i];
  fout<<'\n';
}
void Suma(NrMare x, int lgx, NrMare y, int lgy, NrMare z, int& lgz)
{int i, t, rez;
 if (lgx<lgy) {lgz=lgy; Zero(x,lgx,lgy);}
    else {lgz=lgx; Zero(y,lgy,lgx);}
 for (i=t=0; i<lgz; i++ )
     {
      rez=x[i]+y[i]+t;
      z[i]=rez%10;
      t=rez/10;
     }
  if (t) z[lgz++]=t;
}
void Zero(NrMare x, int st, int dr)
{ int i;
  for (i=st; i<dr; i++) x[i]=0;
}
void combinari()
{int i, j;
 lp=0, lc=1;
 C[0][0][0]=1;lg[0][0]=1; C[0][1][0]=1; lg[0][1]=1; C[1][0][0]=1; lg[1][0]=1;
 for (i=2; i<=n; i++)
     {
     for (j=1; j<i; j++)
        Suma(C[lp][j],lg[lp][j], C[lp][j-1], lg[lp][j-1], C[lc][j], lg[lc][j]);
     C[lc][i][0]=1; lg[lc][i]=1;
     lp=1-lp; lc=1-lc;
     }
}
void genereaza()
{int i, j;
 for (i=1; i<=K; i++) sol[i]=i;
 for (j=2; j<=P; j++)
     {///succesor
     for (i=K; sol[i]==n-K+i; i--);
     sol[i]++;
     for (i++; i<=K; i++) sol[i]=1+sol[i-1];
     }
}
void arce()
{int i, j, nr=0;
 for (i=1; i<=N; i++)
     for (j=1; j<=N; j++)
          if (i!=j) {++nr; a[nr].x=i; a[nr].y=j;}
}
void afiseaza_sol()
{int i;
 for (i=1; i<=K; i++)
      fout<<a[sol[i]].x<<' '<<a[sol[i]].y<<'\n';
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3379)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3379/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3379/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)