yipo
5/31/2014 - 4:04 PM

## To Add or to Multiply

``````#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=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);

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;
}

``````