To Add or to Multiply

The number of multiplications is pretty small total. So assume some number of multiplications, then try inserting adds as early as possible in the multiplication stream in order to stay below the target value. Iterate over all possible counts of multiplications to find the minimum.

Watch out for overflow.

import java.util.*;
public class a {
	Scanner in=new Scanner(System.in);
	long a,m,p,q,r,s;
	public static void main(String[] args) {
		new a().go();
	}
	private void go() {
		int cnum=0;
		while(true){
			cnum++;
			a=in.nextLong();
			m=in.nextLong();
			p=in.nextLong();
			q=in.nextLong();
			r=in.nextLong();
			s=in.nextLong();
			if(a==0&&m==0)break;
			if(p>=r&&p<=s&&q>=r&&q<=s){
				System.out.printf("Case %d: empty\n",cnum);
				continue;
			}
			long mult=0;
			ArrayList<long[]> l=new ArrayList<long[]>();//calculate best solution for any given number of multiplies
			while(true){//probably should be a for loop over # multiplies...whatever
				if((q-p)*Math.pow(m, mult)>(s-r)||mult>30)break;
				long[] test=new long[(int) (mult+1)];
				long lo=p;
				long hi=q;
				for(int i=0;i<test.length;i++){
					if(lo<0||hi<0)break;
					test[i]=Math.max(0,(long) ((r/Math.pow(m,test.length-i-1)-lo)/a));
					while((lo+a*test[i])*Math.pow(m, test.length-i-1)<r&&(hi+a*(test[i]+1))*Math.pow(m, test.length-i-1)<=s)test[i]++;
					lo+=a*test[i];
					lo*=m;
					hi+=a*test[i];
					hi*=m;
				}
				if(lo/m>=r&&hi/m<=s)l.add(test);
				mult++;
			}
			if(l.size()==0){
				System.out.printf("Case %d: impossible\n",cnum);
				continue;
			}
			long min=Long.MAX_VALUE;
			long[] ans={};
			for(long[] i:l){//choose shortest one...apparently this happens to work for lexicographical too....
				long count=i.length-1;
				for(long j:i)count+=j;
				if(count<min){
					min=count;
					ans=i;
				}
			}
			String out=String.format("Case %d: ",cnum);//printing is a bitch
			int mm=0;//number of multiplies built up
			for(int i=0;i<ans.length;i++){
				if(ans[i]!=0){//we have adds to add
					if(i!=0)out+=mm+"M ";//if we have multiplies built up, write them first
					out+=ans[i]+"A ";//write all the adds
					if(i<ans.length-1){//unless its the last add, we start over with 1 multiply
						mm=1;
					}else{
						mm=0;
					}
					continue;
				}
				if(i<ans.length-1)mm++;//or just add a multiply
			}
			if(mm!=0)out+=mm+"M ";//print the last multiplies if there are any
			System.out.println(out.substring(0,out.length()-1));//truncate the last space
		}
	}
}
//To Add or to Multiply
//math
//longs
//output
//overflow