Cod sursa(job #160626)

Utilizator rethosPaicu Alexandru rethos Data 16 martie 2008 13:26:22
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define NM 101
int n,m,a[NM][NM];
struct chestie{int grad,nod;} ain[NM],aout[NM];
void swap(chestie c[],int x,int y)
{ chestie aux=c[x];
  c[x]=c[y];
  c[y]=aux;
}
void qsort(chestie c[],int st,int dr)
{ if (st>=dr) return;
  int t=st,i;
  for (i=st+1;i<=dr;i++)
	if (c[i].grad>c[st].grad) swap(c,i,++t);
  swap(c,st,t);
  qsort(c,st,t-1);
  qsort(c,t+1,dr);
}
int main()
{ freopen("harta.in","r",stdin);
  freopen("harta.out","w",stdout);
  scanf("%d",&n);
  int i;
  for (i=1;i<=n;i++)
	{ scanf("%d %d",&aout[i].grad,&ain[i].grad);
	  aout[i].nod=ain[i].nod=i;
	  m+=ain[i].grad;
	  a[i][i]=-1;
	}
  qsort(ain,1,n);
  qsort(aout,1,n);
  printf("%d\n",m);
  int x,y;
  while (m)
	{ m--;
	  x=aout[1].nod;
	  y=ain[1].nod;i=1;
	  while (a[x][y]) { i++;y=ain[i].nod;}
	  a[x][y]=1;
	  printf("%d %d\n",x,y);
	  aout[1].grad--;
	  ain[i].grad--;
	  for (i=1;i<n;i++) if (aout[i].grad<=aout[i+1].grad) swap(aout,i,i+1);
	  for (i=1;i<n;i++) if (ain[i].grad<=ain[i+1].grad) swap(ain,i,i+1);
	}
  return 0;
}