// 表達式中插入乘號問題
# include<stdio.h>
# include<stdlib.h>
# include<math.h>
int N,R;          //N存放總個數,R乘需要插入乘號的個數
double MAX=0;          
char c[100];     //用來存放輸入的表達式
int a[100],b[100];

int change(int left,int right)  //將字符串轉換成數字
{
	int i,wei=right-left,s=0;
	for(i=left;i<=right;i++,wei--)
	{
	  //s=s+pow(c[i]-48,wei);
	    s=s+(c[i]-48)*pow(10,wei);
	}
	return s;
}

int max(void)    //更新最大值的實現
{
	int k=1,i;
	double s=1;
	for(i=1;i<=R;i++)
	{
		s=s*change(k,a[i]);
		k=a[i]+1;
	}
	s=s*change(k,N);
	if(s>MAX)
	{
		MAX=s;
		for(i=1;i<=N;i++)
			b[i]=a[i];
	}
	return 0;
}


int combine(int n,int r)   //遞歸求組合數
{
	int i;
	if(n<r)               //輸入數據有誤
		return 0;
	else if(r<1)          //組合數已經完全確定
		max();
	else                 //繼續填充組合數
	{
		for(i=n;i>=r;i--)
		{
			a[r]=i;
			combine(i-1,r-1);
		}
	}
	return 0;
}


int print(void)    //輸出滿足要求的結果
{
	int i,j,k=1;
	printf("%.0f=",MAX);
	for(i=1;i<=R;i++)
	{
		for(j=k;j<=b[i];j++)
			printf("%c",c[j]);
		printf("*");
		k=b[i]+1;
	}

	for(j=k;j<=N;j++)
		printf("%c",c[j]);
	return 0;
}

int main(void)
{
	int i;
	printf("請輸入表達式的長度,即待查入乘號的個數:\n");
	scanf("%d%d",&N,&R);
	getchar();
	printf("請輸入這個表達式:\n");
	for(i=1;i<=N;i++)
		scanf("%c",&c[i]);
	combine(N-1,R);
	//printf("you are a good boy!\n");
	print();
	printf("\n");
    return 0;
}