Pagini recente » Cod sursa (job #2772933) | Cod sursa (job #219360) | Cod sursa (job #1374280) | Cod sursa (job #1993788) | Cod sursa (job #204599)
Cod sursa(job #204599)
#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);
}
}