#include<stdio.h>
#include<stdlib.h>

#define SIZE 21

int read();
int isPossible();

int main(){
  while(read())
    printf("%s\n",isPossible()?"Possible":"Impossible");
  return 0;
}

static int q[SIZE],p[SIZE];
static int n,cost;


int compare(void const* a,void const* b){
  return *(int*)a-*(int*)b;
}

int read(){
  if(scanf("%d %d",&n,&cost)!=2)
    return 0;
  int i;
  for(i=0;i<n;i++)
    if(scanf("%d",q+i)!=1)
      return 0;
  for(i=0;i<n;i++)
    if(scanf("%d",p+i)!=1)
      return 0;
  qsort(q,n,sizeof(int),compare);
  qsort(p,n,sizeof(int),compare);
  return 1;
}

int getRMaxCost(int i,int*v){
        /* 计算剩下的最大值 */
  int r_max_cost=0,j,k;
  for(j=i,k=1;j<n;j++){
    while(k<=n && v[k])
      k++;
    if(k<=n)
      r_max_cost+=q[k-1]*p[j];
    k++;
  }
  return r_max_cost;
}

int getRMinCost(int i,int*v){
        /* 计算剩下的最小值 */
  int r_min_cost=0,j,k;
  for(j=i,k=n;j<n;j++){
    while(k>0 && v[k])
      k–;
    if(k>0)
      r_min_cost+=q[k-1]*p[j];
    k–;
  }
  return r_min_cost;
}

int isPossible(){
  int v[SIZE]={0};
  int log[SIZE]={0};
  int i=0,sum=0,add;
  int r_max_cost,r_min_cost;
  int j,k;
  while(i>=0){

    v[log[i]]=0;
    log[i]++;

    while( v[log[i]] && log[i]<=n )
      log[i]++;

    if(log[i]<=n){

      if(i==n-1 && sum+q[log[i]-1]*p[i]==cost)
        return 1;

      else{

        r_max_cost=getRMaxCost(i,v);
        r_min_cost=getRMinCost(i,v);

        if(sum+r_max_cost<cost ||
           sum+r_min_cost>cost){
          i–;
          if(i>=0)
            sum-=q[log[i]-1]*p[i];
          continue;
        }
        /* 是否是一可行解 */
        if(sum+r_min_cost==cost ||
           sum+r_max_cost==cost)
          return 1;
        /* 记录当前状态 */
        sum+=q[log[i]-1]*p[i];
        v[log[i]]=1;
        i++;
        log[i]=0;
      }
    }else{
      /* 回溯 */
      i–;
      if(i>=0)
        sum-=q[log[i]-1]*p[i];
    }
  }
  return 0;
}


评论

该日志第一篇评论

发表评论

评论也有版权!