2015
04-10

The two trains each contain some railroad cars. Each railroad car contains a single type of products identified by a positive integer up to 1,000,000. The two trains come in from the right on separate tracks, as in the diagram above. To combine the two trains, we may choose to take the railroad car at the front of either train and attach it to the back of the train being formed on the left. Of course, if we have already moved all the railroad cars from one train, then all remaining cars from the other train will be moved to the left one at a time. All railroad cars must be moved to the left eventually. Depending on which train on the right is selected at each step, we will obtain different arrangements for the departing train on the left. For example, we may obtain the order 1,1,1,2,2,2 by always choosing the top train until all of its cars have been moved. We may also obtain the order 2,1,2,1,2,1 by alternately choosing railroad cars from the two trains.

To facilitate further processing at the other train yards later on in the trip (and also at the destination), the supervisor at the train yard has been given an ordering of the products desired for the departing train. In this problem, you must decide whether it is possible to obtain the desired ordering, given the orders of the products for the two trains arriving at the train yard.

The input consists of a number of cases. The first line contains two positive integers N1 N2 which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N1 positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N2 positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N1+N2 positive integers giving the desired order for the departing train (same format as above).

The end of input is indicated by N1 = N2 = 0.

The input consists of a number of cases. The first line contains two positive integers N1 N2 which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N1 positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N2 positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N1+N2 positive integers giving the desired order for the departing train (same format as above).

The end of input is indicated by N1 = N2 = 0.

3 3
1 2 1
2 1 1
1 2 1 1 2 1
3 3
1 2 1
2 1 2
1 1 1 2 2 2
0 0

possible
not possible

< [if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 70    Accepted Submission(s): 24

Problem Description

The two trains each contain some railroad cars. Each railroad car contains a single type of products identified by a positive integer up to 1,000,000. The two trains come in from the right on separate tracks, as in the diagram above. To combine the two trains, we may choose to take the railroad car at the front of either train and attach it to the back of the train being formed on the left. Of course, if we have already moved all the railroad cars from one train, then all remaining cars from the other train will be moved to the left one at a time. All railroad cars must be moved to the left eventually. Depending on which train on the right is selected at each step, we will obtain different arrangements for the departing train on the left. For example, we may obtain the order 1,1,1,2,2,2 by always choosing the top train until all of its cars have been moved. We may also obtain the order 2,1,2,1,2,1 by alternately choosing railroad cars from the two trains.

To facilitate further processing at the other train yards later on in the trip (and also at the destination), the supervisor at the train yard has been given an ordering of the products desired for the departing train. In this problem, you must decide whether it is possible to obtain the desired ordering, given the orders of the products for the two trains arriving at the train yard.

Input

The input consists of a number of cases. The first line contains two positive integers N
1
N
2
which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N
1
positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N
2
positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N
1
+N
2
positive integers giving the desired order for the departing train (same format as above).

The end of input is indicated by N
1
= N
2
= 0.

Output

For each case, print on a line possible if it is
possible
to produce the desired order, or
not possible
if not.

Sample Input

3 3

1 2 1

2 1 1

1 2 1 1 2 1

3 3

1 2 1

2 1 2

1 1 1 2 2 2

0 0

Sample Output

possible

not possible

8

n1

n2

……

ps：为神马看到铁路总想起栈？？呃
……

……

f(int t1,int t2,int t)

t1

t1

t2

t2

t

if(tt==n+m){ok=1; return;}
if(t1<n && a[t1]==c[tt])f(t1+1, t2, tt+1);
if(t2<m && b[t2]==c[tt])f(t1,t2+1,tt+1);

1
，如果是，表示
possible
，不是表示
not possible
，但是悲催的这样
tle

……

p[i][j]

i

j

1
，否则置
0.

return

1 1 2 3

1 2 3 1

（显然不成立吧

f(0,0,0)->f(1,0,1)->f(2,0,2)->
f(2,1,3)

（没满足了呃……

->f(2,0,2)->f(1,0,1)->f(1,1,2)->

f(2,1,3)

（呃……

……

，这样就能过了
……

#include<stdio.h>
int a[1005],b[1005],c[2005];
int p[1005][1005];
int n,m;
int ok;
int t;
void f(int t1,int t2,int tt)
{
int i;
if(ok) return;
if (p[t1][t2]==1) return;
if(tt==n+m)
{
ok=1; return;
}
if(t1<n && a[t1]==c[tt])
{
f(t1+1, t2, tt+1);
}
if(t2<m && b[t2]==c[tt])
{
f(t1,t2+1,tt+1);
}
p[t1][t2]=1;
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
for(i=0; i<n; i++) scanf("%d",&a[i]);
for(i=0; i<m; i++) scanf("%d",&b[i]);
for(i=0; i<n+m; i++) scanf("%d",&c[i]);
ok=0;
for (i=0;i<=n;i++)
{
for (j=0;j<=m;j++)
{
p[i][j]=0;
}
}
f(0,0,0);
if(ok==1)
printf("possible/n");
else
printf("not possible/n");
}
return 0;
}



1. 博物说天天鉴定戴胜很烦，然后有人说哪天非要找个戴胜吃夹竹桃天蛾幼虫的图片给博物君辨认（这两者都是很猎奇但是很普遍天天被人@要鉴定的），博物说夹竹桃天蛾幼虫有毒戴胜不会吃，然后就有了童鞋PS了这张图出来。