To Add or to Multiply

1101.cpp

#include <vector>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;

typedef long long lint;
const int INF=1<<30;

inline int pow(int base,int exp) {
	int num=1;
	while (exp--) num*=base;
	return num;
}

int highest_power(int m,int q,int s) {
	if (m<=1) return 0;
	if (q<=0) return INF;
	lint power=m;
	int n=0;
	while (q*power<=s) power*=m,n++;
	return n;
}

vector<int> polynomial_at_least_value(int value,int a,int m,int k) {
	vector<int> poly(1+k);
	int remain=value%a;
	value/=a;
	if (remain>0) value++;
	for (int i=0;i<k;i++) {
		poly[i]=value%m;
		value/=m;
	}
	poly[k]=value;
	return poly;
}

int value_polynomial(int a,int m,int q,const vector<int> &poly) {
	int k=poly.size()-1;
	int value=q*pow(m,k);
	for (int i=0;i<=k;i++) value+=poly[i]*a*pow(m,i);
	return value;
}

void print_polynomial(const vector<int> &poly) {
	cout<<":";
	for (int i=0;i<poly.size();i++) cout<<" "<<poly[i];
	cout<<endl;
}

void enhance_poly(int a,int m,int s,int value,vector<int> &poly) {
	int k=poly.size()-1;
	for (int i=0;i<k;i++) {
		if (poly[i]%m>0) {
			int bonus=m-poly[i]%m;
			lint score=(lint)bonus*a*pow(m,i);
			if (value+score<=s) {
				poly[i]+=bonus;
				value+=score;
			}
		}
		poly[i+1]+=poly[i]/m;
		poly[i]%=m;
	}
}

int num_of_add_op(const vector<int> &poly) {
	int num=0;
	for (int i=0;i<poly.size();i++) num+=poly[i];
	return num;
}

string string_poly(const vector<int> &poly) {
	if (poly.size()==0) return "impossible";
	if (poly.size()==1&&poly[0]==0) return "empty";
	
	ostringstream oss;
	int k=poly.size()-1;
	int pre=k;
	bool first=true;
	if (poly[k]>0) oss<<poly[k]<<"A",first=false;
	for (int i=k-1;i>=0;i--) {
		if (poly[i]>0||i==0) {
			oss<<(first?"":" ")<<(pre-i)<<"M";
			if (poly[i]>0) oss<<" "<<poly[i]<<"A";
			pre=i;
			first=false;
		}
	}
	return oss.str();
}

string gen_program(int a,int m,int p,int q,int r,int s) {
	int k=min(
		highest_power(m,q,s),
		highest_power(m,q-p,s-r)
	);
	
	int min_arg=INF;
	vector<int> min(0);
	for (int i=0;i<=k;i++) {
		int distance=r-p*pow(m,i);
		if (distance<0) distance=0;
		
		vector<int> poly=polynomial_at_least_value(distance,a,m,i);
		int value=value_polynomial(a,m,q,poly);
		if (s<value) continue;
		enhance_poly(a,m,s,value,poly);
		
		int alt=i+num_of_add_op(poly);
		if (alt<min_arg) {
			min_arg=alt;
			min=poly;
		}
	}
	return string_poly(min);
}

int main() {
	int k=1,a,m,p,q,r,s;
	while (cin>>a>>m>>p>>q>>r>>s) {
		if (a==0&&m==0&&p==0&&q==0&&r==0&&s==0) break;
		cout<<"Case "<<k++<<": "<<gen_program(a,m,p,q,r,s)<<endl;
	}
	return 0;
}