#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct nod
{
long long info;
nod *st,*dr;
};
void citire(FILE *f,long &n,nod **&c1)
{
fscanf(f,"%ld",&n);
c1=(nod**)malloc((n+1)*sizeof(nod**));
c1[0]=(nod*)malloc(sizeof(nod));
for(long i=1;i<=n;i++)
{
c1[i]=(nod*)malloc(sizeof(nod));
fscanf(f,"%lld",&c1[i]->info);
c1[i]->st=c1[i]->dr=NULL;
}
}
void addQueue(nod *r,nod **&c,long &st,long &dr)
{
dr++;
c[dr]=(nod*)malloc(sizeof(nod));
c[dr]=r;
}
int emptyQueue(nod **c,long st,long dr)
{
if(dr<st)
return 1;
return 0;
}
nod* extrageMin(nod **&c1,nod **&c2,long &st1,long &dr1,long &st2, long &dr2)
{
nod *min;
if(emptyQueue(c2,st2,dr2))
min=c1[st1++];
else
if(emptyQueue(c1,st1,dr1))
min=c2[st2++];
else
if(c1[st1]->info<=c2[st2]->info)
min=c1[st1++];
else
min=c2[st2++];
return min;
}
nod* creareHuffman(long n,nod **c1,long long &lg)
{
lg=0;
nod **c2=(nod**)malloc((n+1)*sizeof(nod*));
nod *x,*y,*r;
long st1=1,dr1=n,st2=1,dr2=0,i;
for(i=1;i<=n-1;i++)
{
x=extrageMin(c1,c2,st1,dr1,st2,dr2);
y=extrageMin(c1,c2,st1,dr1,st2,dr2);
r=(nod*)malloc(sizeof(nod));
r->info=x->info+y->info;
r->st=x;
r->dr=y;
lg+=r->info;
addQueue(r,c2,st2,dr2);
}
r=c2[st2];
return r;
}
void coduri(nod *r,long long cod,long nivel,FILE *g)
{
if(r->st)
{
coduri(r->st,cod*2,nivel+1,g);
coduri(r->dr,cod*2+1,nivel+1,g);
return;
}
fprintf(g,"%ld %lld\n",nivel,cod);
}
int main()
{
FILE *f=fopen("huffman.in","r");
FILE *g=fopen("huffman.out","w");
nod **c1,*r;
long n;
long long lg;
citire(f,n,c1);
r=creareHuffman(n,c1,lg);
fprintf(g,"%lld\n",lg);
coduri(r,0,0,g);
fclose(g);
fclose(f);
return 0;
}