사고방식: 먼저 모든 열차가 각 역을 지나가는 시간 방향을 처리해야 한다.그다음에 시뮬레이션이야.
/*****************************************
Author :Crazy_AC(JamesQi)
Time :2015
File Name :
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#define MEM(a,b) memset(a,b,sizeof a)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> ii;
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
inline int Readint(){
char c = getchar();
while(!isdigit(c)) c = getchar();
int x = 0;
while(isdigit(c)){
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
const int maxn = 1e3 + 10;
int mx[maxn],my[maxn],dp[maxn][maxn],t[maxn];
bool is[maxn][maxn][2];
int m1,m2;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,icase = 0;
while(scanf("%d",&n) != EOF && n){
// cout << "n = " << n << endl;
memset(is, false,sizeof is);
int tt;
scanf("%d",&tt);
for (int i = 1;i < n;i++)
cin >> t[i];
scanf("%d",&m1);
for (int i = 1;i <= m1;++i)
scanf("%d",&mx[i]);
scanf("%d",&m2);
for (int j = 1;j <= m2;++j)
scanf("%d",&my[j]);
for (int j = 1;j <= m1;++j){
int sum = 0;
is[mx[j]][1][0] = true;
for (int i = 1;i < n;i++){
sum += t[i];
is[sum + mx[j]][i + 1][0] = true;
}
}
for (int j = 1;j <= m2;++j){
int sum = 0;
is[my[j]][n][1] = true;
for (int i = n - 1;i > 0;--i){
sum += t[i];
is[my[j] + sum][i][1] = true;
}
}
memset(dp, 0,sizeof dp);
for (int i = 1;i <= n - 1;i++) dp[tt][i] = inf;
dp[tt][0] = 0;
for (int i = tt - 1;i >= 0;--i){
for (int j = 1;j <= n;j++){
dp[i][j] = dp[i + 1][j] + 1;
if (j < n && is[i][j][0] && i + t[j] <= tt){
dp[i][j] = min(dp[i][j],dp[i + t[j]][j + 1]);
}
if (j > 1 && is[i][j][1] && i + t[j - 1] <= tt){
dp[i][j] = min(dp[i][j],dp[i + t[j - 1]][j - 1]);
}
}
}
printf("Case Number %d: ",++icase);
if (dp[0][1] >= INF) puts("impossible");
else printf("%d
",dp[0][1]);
}
return 0;
}