Cod sursa(job #204599)

Utilizator marinMari n marin Data 25 august 2008 17:14:32
Problema Taramul Nicaieri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#define DIM 102

struct inter {
  long int a;
  long int b;
};

typedef inter tip;


tip dp[DIM];
tip dm[DIM];
int a[DIM][DIM];

int n,tot,i,j,x,y;


void cre(tip *v, long int n);
void corect(long int poz, tip *v, long int n);
void sort(tip *v, long int n);



int main(){
  FILE *f = fopen("harta.in","r");
  fscanf(f,"%ld",&n);
  for (i=1;i<=n;i++) {
    fscanf(f,"%ld %ld",&x,&y);
	dp[i].a=i;
	dp[i].b=x;
	dm[i].a=i;
	dm[i].b=y;
  }
  sort(dp,n);
  tot=0;
  for (i=n;i>=1;i--) {
    sort(dm,n);
    for (j=n;j>=1;j--) {
      if ((dp[i].b!=0) && (dp[i].a!=dm[j].a)) {
	dp[i].b--;
	a[dp[i].a][dm[j].a]=1;
	dm[j].b--;
	tot++;
	if (dp[i].b==0)
	  break;
      }

    }
  }
  FILE *g = fopen("harta.out","w");
  fprintf(g,"%d\n",tot);
  for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
	  if (a[i][j]==1)
	    fprintf(g,"%d %d\n",i,j);
  fclose(g);

  return 0;
}






void cre(tip *v, long int n){
  long int i,c,p;
  tip aux;
  for (i=2;i<=n;i++) {
    c = i;
    p = i>>1;
    while ((p)&&(v[c].b>v[p].b)) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      c = p;
      p = p>>1;
    }
  }
}

void corect(long int poz, tip *v, long int n){
  long int p,c;
  tip aux;
  p = poz;
  c = p<<1;
  while (c<=n) {
    if ((c+1<=n) && (v[c+1].b>v[c].b))
      c++;
    if (v[c].b>v[p].b) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      p = c;
      c = p<<1;
    } else break;
  }

}

void sort(tip *v, long int n) {
  long int i;
  tip aux;
  cre(v,n);
  for (i=n;i>1;i--) {
    aux = v[1];
    v[1] = v[i];
    v[i] = aux;
    corect(1,v,i-1);
  }
}