2015
05-23

# Judges’ response

The contest is running and the judges is busy watching the progress of the contest. Suddenly, N – 1 (N <= 16) contestants hand up their hand at the same time. The judges should go to answer the contestants’ question one by one. The judges already foresee that answering contest i’s question would cost Ci minutes. In order to serve all the contestant, each judges is assigned to serve some subset of the contestants. As the judges have limited patience, each one of them can serve the contestants for no more than M minutes.
You are asked to solve two problems:
1. At least how many judges should be sent so that they can serve all the contestants? (Because the judges have limited patience, each one of them cannot serve too many contestants.)
2. If there are infinite number of judges, how to assign the route for each judge so that the sum of their walking time is minimized? Each contestant i is reside in place (xi, yi), the judges are in place (x1, y1). Assuming the walking speed of the judge is 1.

There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i’s question. C1 will 0 as place 1 is for the judges.

The distance between place i and place j is defined as ceil(sqrt((xi – xj) ^ 2 + (yi – yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i’s question. C1 will 0 as place 1 is for the judges.

The distance between place i and place j is defined as ceil(sqrt((xi – xj) ^ 2 + (yi – yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

3 3
0 0
0 3
0 1
0
1
2

3 2
0 0
0 3
0 1
0
1
2

3 1
0 0
0 3
0 1
0
1
2

16 35
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11

1 6
2 8
-1 -1
8 467

by—cxlove

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#define inf 1<<28
#define M 100005
#define N 55
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Point{
int x,y;
}p[20];
int n,m,val[20],path[20][20];
int dp[16][1<<16],state[1<<16],tot;
int best[1<<16],ok[1<<16];
int dist(Point p1,Point p2){
return ceil(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
void Get_dist(){
for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=dist(p[i],p[j]);
}
void Init(){
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
dp[i][j]=inf;
for(int i=0;i<(1<<n);i++)
best[i]=inf;
dp[0][1]=0;
}
int check(int state){
int sum=0;
for(int i=0;i<n;i++)
if(state&(1<<i))
sum+=val[i];
return sum<=m;
}
bool cmp(int a,int b){return a>b;}
int slove(){
int dp[1<<16];
for(int i=0;i<(1<<n);i++) dp[i]=inf;
dp[0]=0;
for(int i=0;i<tot;i++){
for(int j=(1<<n)-1;j>=0;j--){
if(dp[j]==inf) continue;
if(state[i]&j) continue;
dp[state[i]+j]=min(dp[state[i]+j],dp[j]+1);
}
}
return dp[(1<<n)-1]==inf?-1:dp[(1<<n)-1];
}
int TSP(){
for(int i=0;i<(1<<n);i++){
if(ok[i])
for(int j=0;j<n;j++)
if(i&(1<<j)){
best[i]=min(best[i],dp[j][i]+path[j][0]);
for(int k=0;k<n;k++)
if(!(i&(1<<k)))
dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+path[j][k]);
}
}
for(int i=0;i<(1<<n);i++)
if(i&1)
for(int j=i&(i-1);j;j=i&(j-1))
best[i]=min(best[i],best[j]+best[(i-j)|1]);
return best[(1<<n)-1];
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
tot=0;
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++) scanf("%d",&val[i]);
for(int i=0;i<(1<<n);i++) {
ok[i]=check(i);
if(ok[i])
state[tot++]=i;
}
Get_dist();
Init();
int ans1=slove();
if(ans1==-1) {printf("-1 -1\n");continue;}
printf("%d %d\n",ans1,TSP());
}
return 0;
}