poj 1010

/*
Sample Input

1 2 3 0    ; three different stamp types
7 4 0        ; two customers
1 1 0        ; a new set of stamps (two of the same type)
6 2 3 0    ; three customers
Sample Output

7 (3): 1 1 2 3 
4 (2): 1 3 
6 ---- none
2 (2): 1 1
3 (2): tie
*/
#include
#include
#include
using namespace std;
int data[100],cnt,customer;
bool none,tie;
int now[5],now_type,now_num,now_max,end[5],end_type,end_num,end_max;
int get_type(int a[],int n){
    sort(a,a+n);
    int i,type = 0;
    if(n>0)type = 1; 
    for(i=1;i){
        if(a[i]!=a[i-1]){
            type++;
        }
    }
    return type;
}
int get_max(int a[],int n){
    int i,m_a = -9999;
    for(i=0;i){
        if(m_a<data[a[i]]){
            m_a = data[a[i]];
        }
    }
    return m_a;
}
void print(){
    int i;
    printf("%d ",customer);
    if(none){
        printf("---- none\n");
    }
    else{
        printf("(%d): ",get_type(end,end_num));
        if(tie){
            printf("tie\n");
        }
        else{
            sort(end,end+end_num);
            for(i=0;i1;i++){
                printf("%d ",data[end[i]]);
            }
            printf("%d\n",data[end[i]]);
        }
    }
}
void compare(){
    int i;
    now_type = get_type(now,now_num);
    now_max = get_max(now,now_num);
    end_type = get_type(end,end_num);
    end_max = get_max(end,end_num);
    if((end_num==0)||(end_typenow_num)||(end_type==now_type&&end_num==now_num&&end_max<now_max)){
        tie = false;
        end_num = now_num;
        for(i=0;i){
            end[i] = now[i];
        }
    }
    else if(end_type==now_type&&end_num==now_num&&end_max==now_max){
         tie = true;
    }
}
int dfs(int n,int value){
    int i;
    if(value>customer)return 0;
    if(value==customer){
        none = false;
        compare();
    }
    if(now_num==4)return 0;
    for(i=n;i){
        now[now_num] = i;
        now_num++;
        dfs(i,value+data[i]);
        now_num--;
    }
}
char suffix[100];
int main(){
    int i;
    while(true){
        cnt = 0;
        memset(now,0,sizeof(now));
        memset(end,0,sizeof(end));
        while(true){
            if(scanf("%d",&data[cnt])==EOF)return 1;
            if(data[cnt]==0)break;
            cnt++;
        }
        sort(data,data+cnt);
        gets(suffix);
        while(true){
            if(scanf("%d",&customer)==1&&customer==0){
                break;
            }
            now_num = 0;
            end_num = 0;
            none = true;
            tie = false;
            dfs(0,0);
            print();
        }
        gets(suffix);
    }
    return 0;
}