#include <stdio.h>
#include <stdlib.h>

typedef struct { int n,d,i; } scale_wrk;
int scale_cmp(const void* lv,const void *rv) {
    scale_wrk *x=(scale_wrk *)lv, *y=(scale_wrk *)rv;
    int u=x->n*y->d, v=y->n*x->d;
    return u==v ? (x->i > y->i) : u > v;
}
void scale(int n,int *x,int *w,int D,scale_wrk *t) {
    int d,i,s,k;
    s=0;for(i=0;i<n;i++) s+=x[i];
    d=0;for(i=0;i<n;i++) {
        d+=w[i]=x[i]*D/s; 
        t[i].n=w[i]+1; t[i].d=x[i]; t[i].i=i; 
    }
    if (d>=D) return;
    qsort(t,n,sizeof(*t),scale_cmp);
    for(k=0;;) {
        i=t[k].i; w[i]++; if (++d>=D) break; ++t[k].n;
        if (scale_cmp(t+k,t+n-1)) k++;
        else { 
            if (scale_cmp(t+k,t+k+1))
                qsort(t+k,n-k,sizeof(*t),scale_cmp); 
        }
    }
}

int main(int argc,char **argv) {
    enum { n=5 };
    scale_wrk t[n];
    int i,D,w[n],x[n]={ 30,3,3,31,30 };
    for(D=1;D<=200;D++) {
        scale(n,x,w,D,t);
        printf("%3d:",D);
        for(i=0;i<n;i++) printf(" %2d",w[i]);
        printf("\n");
    }
    return 0;
}