Cod sursa(job #174766)

Utilizator DorinOltean Dorin Dorin Data 9 aprilie 2008 11:17:17
Problema Taramul Nicaieri Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
# include <stdio.h>

# define input "harta.in"
# define output "harta.out"

# define max 101

int n,i,j,in[max],out[max],m;
int u[max][max],nr,k, x, y;

struct muchie
{
    int x,y;
}v[20001];

int main()
{
    freopen(input,"r", stdin);
    freopen(output,"w",stdout);
    
    scanf("%d",&n);
    
    for(i = 1;i<=n; i++)
    {
        scanf("%d%d",&out[i],&in[i]);
        m+= in[i];
    }
    printf("%d\n",m);
        
    for ( i = 1; i <= n; i++)
        for ( j = 1; j <= n && out[i]; j++)
            if(i != j && in[j])
            {
                 v[++nr].x = i;
                 v[nr].y = j;
                 u[i][j] = 1;
                 out[i] --;
                 in[j] --;
            }
            
    for ( i = 1; i<= n; i++)
      if(out[i])
      {
          for ( j = 1; j <= n; j++)
             if(in[j]) break;
          for ( k = 1; k <= nr; k++)
          {
              x = v[k].x;
              y = v[k].y;
              if(!u[x][j] && !u[i][y])
              {
                  u[x][j] = u[i][y] = 1;
                  u[x][y] = 0;
                  v[k].y = j;
                  v[++nr].x = i;
                  v[nr].y = y;
                  break;
              }
          }
          in[j]--;
          out[i]--;
          i--;
      }
      
    if(nr != m) while(1);
    for(i = 1; i<=nr;i++)
       printf("%d %d\n",v[i].x,v[i].y);
    
    return 0;
}