// Lucrari pe procesoare

#include <stdio.h>
#include <conio.h>

const nl=100;
const np=50;

typedef struct nod
{
	int lucr;
   struct nod*aeu;
}NOD;

typedef struct
{
	float g;
   NOD *adr;
}elem;

void ord_desc(float t[],int m,int l[])
{
	int i,j,k[nl];
   for (i=0;i<m;i++)
   	k[i]=0;
   for (i=0;i<=m-2;i++)
   	for (j=i+1;j<=m-1;j++)
      	if (t[i]>=t[j]) k[j]++;
         else k[i]++;           // k[i]=nr. de elemente mai mari ca i
   for (i=0;i<m;i++)
   	l[k[i]]=i;
}

int minim(elem p[],int n)
{
	float min=p[0].g;
   int ip=0,i;
   for(i=1;i<n;i++)
   	if(p[i].g<min)
      {
      	min=p[i].g;
         ip=i;
      }
   return ip;
}

void repart(int il,float t,int ip,elem p[])
{
	p[ip].g+=t;
   NOD *q=p[ip].adr;
   while(q->aeu)
   	q=q->aeu;
   NOD *r=new NOD;
   r->lucr=il+1;
   r->aeu=0;
   q->aeu=r;
}

void afis(elem p[],int n)
{
	NOD *q;
	for(int i=0;i<n;i++)
   {
    	printf("\nProcesorul %d :\n- durata de functionare : %g\n-lucrarile executate : ",i+1,p[i].g);
      q=p[i].adr;
      while(q)
      {
      	printf("%d ",q->lucr);
         q=q->aeu;
      }
	}
}

float maxim(elem p[],int n)
{
   float max=p[0].g;
   for(int i=1;i<n;i++)
   	if(p[i].g>max)
      	max=p[i].g;
   return max;
}

void main()
{
	int n,m,i,j,l[nl];
   float t[nl];
   elem p[np];
   	do
      {
      	fflush(stdin);
			printf("Nr. de procesoare (n>=1) : ");
      }
      while (scanf("%d",&n)!=1 || n<1);
      do
      {
      	fflush(stdin);
			printf("Nr. de lucrari (m>=1) : ");
      }
      while (scanf("%d",&m)!=1 || m<1);
      for (i=0;i<m;i++)
      	do
      	{
      	fflush(stdin);
			printf("Timpul de executie a lucrarii %d : ",i+1);
	      }
   	   while (scanf("%f",&t[i])!=1 || t[i]<=0);
      if(m<=n)
      {
      	for(i=0;i<m;i++)
         {
         	p[i].g=t[i];
            p[i].adr=new NOD;
            p[i].adr->lucr=i+1;
            p[i].adr->aeu=0;
         }
         for(i=m;i<n;i++)
         {
         	p[i].g=0;
            p[i].adr=0;
         }
      }
      else
      {
      	ord_desc(t,m,l);
      	for(i=0;i<n;i++)             // primele cele mai lungi n lucrari sunt repartizate fiecare pe un procesor
         {
         	p[i].g=t[l[i]];
            p[i].adr=new NOD;
            p[i].adr->lucr=l[i]+1;
            p[i].adr->aeu=0;
         }
         for(i=n;i<m;i++)     // restul m-n lucrari
         {
         	j=minim(p,n);  // procesorul j termina primul din cele n procesoare
            repart(l[i],t[l[i]],j,p);
         }
      }
      afis(p,n);
      printf("\nTimpul de executie a ansamblului de lucrari : %g",maxim(p,n));
      getch();
}