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

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)

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema nkgraf:

//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';
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3379 nkgraf

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3379 nkgraf de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3379 nkgraf