2005年11月17日

#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;
}

2005年11月07日

#include<cstdio>
using namespace std;

class Booklet{
private:
 int pages;
public:
 bool read();
 void print();
};

bool Booklet::read(){
 if(scanf("%d",&pages)!=1)
  return false;
 return pages!=0;
}

void Booklet::print(){
 printf("Printing order for %d pages:\n",pages);
 int sheets=(pages%4==0)?(pages/4):(pages/4+1);
 int* book=new int[sheets*4];
 int i,j;
 for(i=1;i<=pages;i++)
  book[i-1]=i;
 for(;i<=sheets*4;i++)
  book[i-1]=0;
 int len=sheets*2;
 int page=1;
 for(i=0,j=sheets*4-1;i<len;i+=2,j-=2,page++){
  if(book[j]!=0 || book[i]!=0)
   if(book[j]==0)
    printf("Sheet %d, front: Blank, %d\n",page,book[i]);
   else if(book[i]==0)
    printf("Sheet %d, front: %d, Blank\n",page,book[j]);
   else
    printf("Sheet %d, front: %d, %d\n",page,book[j],book[i]);
  if(book[j-1]!=0 || book[i+1]!=0)
   if(book[j-1]==0)
    printf("Sheet %d, back : %d, Blank\n",page,book[i+1]);
   else if(book[i+1]==0)
    printf("Sheet %d, back : Blank, %d\n",page,book[j-1]);
   else
    printf("Sheet %d, back : %d, %d\n",page,book[i+1],book[j-1]);
 }
 delete[] book;
 return;
}

int main(){
 Booklet booklet;
 while(booklet.read())
  booklet.print();
 return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;

#define SIZE 20
class Deg{
private:
 map<string,int> list;
 int size;
 int graph[SIZE][SIZE];
 void initGraph();
 void createGraph();
public:
 bool read();
 void print();
};

void Deg::initGraph(){
 int i,j;
 for(i=0;i<SIZE;i++)
  for(j=0;j<SIZE;j++)
   i==j?graph[i][j]=0:graph[i][j]=-1;
}

bool Deg::read(){

 initGraph();

 string name,fri;
 int id=1,degs;
 cin>>size;
 for(int i=0;i<size;i++){
  cin>>name;
  if(list[name]==0)
   list[name]=id++;
  cin>>degs;
  for(int j=0;j<degs;j++){
   cin>>fri;
   if(list[fri]==0)
    list[fri]=id++;
   graph[list[name]-1][list[fri]-1]=1;
  }
 }
 return true;
}

void Deg::print(){

 createGraph();

 int times,i,dis;
 string start,goal;
 cin>>times;
 for(i=0;i<times;i++){
  cin>>start>>goal;
  dis=graph[list[start]-1][list[goal]-1];
  if(dis>0)
   cout<<start<<" is separated from "<<goal<<" by "<<dis-1<<" degrees.";
  else
   cout<<start<<" has no connection to "<<goal<<".";
  cout<<endl;
 }
}

void Deg::createGraph(){
 int i,j,k,dest;
 for(k=0;k<size;k++)
  for(i=0;i<size;i++)
   for(j=0;j<size;j++)
    if(graph[i][k]!=-1 && graph[k][j]!=-1){
     dest=graph[i][k]+graph[k][j];
     if(graph[i][j]==-1)
      graph[i][j]=dest;
     else if(graph[i][j]>dest)
      graph[i][j]=dest;
    }
}

int main(){
 Deg deg;
 deg.read();
 deg.print();
 return 0;
}