2013
12-23

# Tempter of the Bone again

Ignatius found some bones in an ancient maze, which fascinated him a lot. However, when he picked them up, the maze began to shake, and Ignatius could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
Suddenly, Ignatius heard a very very cool voice, and he recognize that it comes from Beelzebub feng5166:“I know that you like bone, and even I know your nick name is wishingbone. Today, I give you a chance to survive: there are N kinds of bones here and the number of each kind bone is enough, their weights are Wi pounds (1<=i<=N), your bag has a volume of M pounds, and I also know that you will spend 3 seconds time when you pick up any one bone. Today, you must fill up your bag as quick as you can, otherwise, the maze is your place of the death!”.
Note: You are guarantied that solution always exist for every test case.

The input consists of multiple test cases. The first line of each test case contains two integers N and M (1 < N < 10; 0 < M < 1000000000), which denote the kinds of the bone and the capacity of the bag respectively. The next line give N integers W1…Wn (1<=wi<=100), which indicate the weights of bones
The input is terminated with two 0′s. This test case is not to be processed.

For each test case, print the minimal time Ignatius will spend when he can survive. One line per case.

2 20
1 5
0 0

12

#include<iostream>
int N,M,W[10];
int cmp(const void *a,const void *b){
return *(int *)b-*(int *)a;
}
int f_min(int x,int y){
if(x==-1)return y;
return x<y?x:y;
}
void get_W(){
int i;
for(i=0;i<N;i++)
scanf("%d",&W[i]);
qsort(W,N,sizeof(int),cmp);
}
int ans(int bag,int s){
int w=W[s],up;
if(bag%w==0)return bag/w;
if(s==N-1)return -1;
up=bag/w;
int lim=f_min(up,W[s+1]-1),i,min=-1,temp;
for(i=0;i<=lim;i++){
temp=ans(bag%w+i*w,s+1);
if(temp==-1)continue;
min=f_min(min,up-i+temp);
}
return min;
}
int main(){
while(scanf("%d%d",&N,&M)&&(N||M)){
get_W();
printf("%d/n",3*ans(M,0));
}
return 0;
}