Cod sursa(job #3075)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 20 decembrie 2006 18:00:24
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.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,ap[NMAX];
	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]);
		
		grad[i][2]=i;
	}

	//qsort(1,n);
	//for (i=1;i<=n;++i) fprintf(out,"%i %i\n",grad[i][0],grad[i][1]);

	for (i=1;i<=n;++i) {
		
		for (j=1;j<=n;++j) ap[j]=0;
		
		x=grad[i][2]; ap[i]=1;
		for (j=i+1;j<=n && grad[i][0];++j) 
			
			if (grad[j][1]) { 
				y=grad[j][2];
				v[x][y]=1;
				++m;
				grad[j][1]--;
				grad[i][0]--;
				//ap[j]=1;
			}
		
		for (j=i+1;j<=n && grad[i][1];++j) 
			
			if (grad[j][0]) { 
				y=grad[j][2];
				v[y][x]=1;
				++m;
				grad[j][0]--;
				grad[i][1]--;
			}
	}

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