Pagini recente » Cod sursa (job #2613812) | Cod sursa (job #165595) | Cod sursa (job #724779) | Cod sursa (job #486130) | Cod sursa (job #3070)
Cod sursa(job #3070)
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define fin "harta.in"
#define fout "harta.out"
#define NMAX 101
int n,m,grad[NMAX][3],v[NMAX][NMAX];
FILE *in,*out;
//0 ext, 1 int
void swap(int &a,int &b) { int aux; aux=a; a=b; b=aux; }
void qsort(int st,int dr) {
int i,j,m;
m=grad[(st+dr)/2][0];
i=st; j=dr;
do {
while (grad[i][0]<m) i++;
while (grad[j][0]>m) j--;
if (i<=j) {
swap(grad[i][0],grad[j][0]);
swap(grad[i][1],grad[j][1]);
swap(grad[i][2],grad[j][2]);
i++; j--;
}
}while (i<j);
if (i<dr) qsort(i,dr);
if (j>st) qsort(st,j);
}
int main() {
int i,j,x,y,aux[NMAX][2];
in=fopen(fin,"r"); out=fopen(fout,"w");
fscanf(in,"%i",&n);
for (i=1;i<=n;++i) {
fscanf(in,"%i%i",&grad[i][0],&grad[i][1]);
}
//qsort(1,n);
//for (i=1;i<=n;++i) fprintf(out,"%i %i\n",grad[i][0],grad[i][1]);
srand(time(0));
do {
for (i=1;i<=n;++i) {
aux[i][0]=grad[i][0];
aux[i][1]=grad[i][1];
}
for (i=1;i<=n;++i)
for (j=1;j<=n;++j) v[i][j]=0;
for (i=1;i<=n;++i) {
while (aux[i][0]) {
y=rand()%n+1;
if (!v[i][y] && !v[y][1] && y!=i) {
v[i][y]=1;
aux[i][0]--;
aux[y][1]--;
}
}
}
/*for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (v[i][j]) {
aux[i][0]++;
aux[j][1]++;
}*/
for (j=1;j<=n && !aux[j][0] && !aux[j][1];++j);
} while (j<=n);
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (v[i][j]) ++m;
fprintf(out,"%i\n",m);
for (i=1;i<=n;i++)
for (j=1;j<=n;++j)
if (v[i][j])
fprintf(out,"%i %i\n",i,j);
fclose(in); fclose(out);
return 0;
}