範例程式碼 uva1101

//uva1101
// uva1101
#include <iostream>
#include<string.h>
#include <math.h> 
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXN 110
using namespace std;

typedef long long LL;
int A, M, P, Q, R, S;

struct Solution
{
    int s;
	int n; 
	int count[MAXN];
    bool A[MAXN];
    
	bool operator < (const Solution &t) const
    {
		if(s != t.s) return s < t.s;
        
		for(int i=0; i<n; i++){
			if(A[i]&&!t.A[i]) return true;
			if(!A[i]&&t.A[i]) return false;
			if(count[i]!=t.count[i]) 
			    return ((count[i]>t.count[i])&&A[i])||(count[i]<t.count[i]&&!A[i]);       
		}
	}
}optimal_solution;


Solution generate_new_soluiton(int a[], int mn)
{
    Solution new_soluiton;
    new_soluiton.s = mn, new_soluiton.n = 0;
    for(int i = 0, &n = new_soluiton.n; i <= mn; i ++)
    {
        new_soluiton.s += a[i];
        if(a[i] > 0)
        {
            new_soluiton.count[n] = a[i], new_soluiton.A[n] = true;
            ++ n;
        }
        if(i < mn)
        {
            if(n == 0 || new_soluiton.A[n - 1])
            {
                new_soluiton.count[n] = 1, new_soluiton.A[n] = false;
                ++ n;
            }
            else ++ new_soluiton.count[n - 1];
        }
    }
   
 return new_soluiton;
}

void generate_soluiton_with_i_Ms(int mn, int p, int px, int py)
{
    if(p > px) px = p;
    LL sum = ((p - px) % A + A) % A + px;
    if(sum > py) return;
    sum = (sum - p) / A;
    int t = sum, max = (py - p) / A, a[MAXN];
    for(int i = mn; i > 0; i --) a[i] = t % M, t /= M;
    a[0] = t;

    Solution new_solution;
    for(int i = mn, fac = 1; i >= 0; i --, fac *= M)
    {
        new_solution = generate_new_soluiton(a, mn);
        
        if(new_solution < optimal_solution) optimal_solution = new_solution;
       
	   
	    if(i > 0 && a[i] != 0)
        {
            sum += (LL)(M - a[i]) * fac, a[i] = M;
            if(sum > max) break;
            for(int j = i; j > 0 && a[j] == M; j --)
                ++ a[j - 1], a[j] = 0;
        }
    }
}


int main()
{
    int rd = 0;

    cin >> A >> M >> P >> Q >> R >> S;
    
	while(!(A==0&&M==0&&P==0&&Q==0&&R==0&&S==0))
	{
    	rd++;
        optimal_solution.s = INF;
        
        LL l = Q - P, p = P;
        for(int i = 0; p <= S - l && l <= S - R; i++)
        {
            generate_soluiton_with_i_Ms(i, p, R, S - l);
            l *= M;
			p *= M;
			if(M == 1) break;
        }
        
        cout <<"Case "<<rd<<":";
        
		if(optimal_solution.s == 0) cout<<" empty"<<endl;  
        else if(optimal_solution.s == INF) cout<<" impossible"<<endl;
        		else
        		{
            		for(int i = 0; i < optimal_solution.n; i ++){
            			cout << " " << optimal_solution.count[i];
						if(optimal_solution.A[i]) 
							cout <<'A';
						else
							cout <<'M';		
					}
            		cout<<endl;
       			}
        cin >> A >> M >> P >> Q >> R >> S;
    }
    return 0;
}