Cod sursa(job #3070)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 20 decembrie 2006 17:41:27
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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;	
}