Cod sursa(job #3081)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 20 decembrie 2006 19:45:52
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#define fin "harta.in"
#define fout "harta.out"
#define NMAX 101
int n,m,grad1[NMAX][4],grad2[NMAX][4],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 qsort2(int st,int dr) {
int i,j,m;
	
	m=grad2[(st+dr)/2][0]+grad2[(st+dr)/2][1];
	i=st; j=dr;
	do {
		while (grad2[i][0]+grad2[i][1]<m) i++;
	       	while (grad2[j][0]+grad2[j][1]>m) j--;
		if (i<=j) { 
			swap(grad2[i][0],grad2[j][0]);	
			swap(grad2[i][1],grad2[j][1]);	
			swap(grad2[i][2],grad2[j][2]);
			i++; j--;
		}
	}while (i<j);
	if (i<dr) qsort2(i,dr);
	if (j>st) qsort2(st,j);
}

void qsort1(int st,int dr) {
int i,j,m;
	
	m=grad1[(st+dr)/2][1];
	i=st; j=dr;
	do {
		while (grad1[i][1]>m) i++;
	       	while (grad1[j][1]<m) j--;
		if (i<=j) { 
			swap(grad1[i][0],grad1[j][0]);	
			swap(grad1[i][1],grad1[j][1]);	
			swap(grad1[i][2],grad1[j][2]);
			i++; j--;
		}
	}while (i<j);
	if (i<dr) qsort1(i,dr);
	if (j>st) qsort1(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",&grad1[i][0],&grad1[i][1]);
		
		grad1[i][2]=grad2[i][2]=i;
		grad2[i][0]=grad1[i][0];
		grad2[i][1]=grad1[i][1];
	}

	qsort1(1,n);
	qsort2(1,n);
	
	/*for (i=1;i<=n;++i) fprintf(out,"%i %i\n",grad1[i][0],grad1[i][1]);
	fprintf(out,"\n");
	for (i=1;i<=n;++i) fprintf(out,"%i %i\n",grad2[i][0],grad2[i][1]);
	*/
	for (i=1;i<=n;++i) {
		
		x=grad2[i][2]; 
		
		for (j=1;j<=n && grad2[i][0];++j) 
			
			if (grad1[j][1] && grad1[j][2]!=x) { 
				y=grad1[j][2];
				v[x][y]=1;
				++m;
				grad1[j][1]--;
				grad2[i][0]--;
			}
		
	}

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