2

11:28:32 02:14:21

05:00:00 96:00:01

Sample Output

09:14:11

04:59:59

1002小明系列故事——女友的考验

Time Limit: 0.2 Seconds   Memory Limit: 32768K

终于放寒假了，小明要和女朋友一起去看电影。这天，女朋友想给小明一个考验，在小明正准备出发的时候，女朋友告诉他，她在电影院等他，小明过来的路线必须满足给定的规则：

1、假设小明在的位置是1号点，女朋友在的位置是n号点，则他们之间有n-2个点可以走，小明每次走的时候只能走到比当前所在点编号大的位置；

2、小明来的时候不能按一定的顺序经过某些地方。比如，如果女朋友告诉小明不能经过1 -> 2 -> 3，那么就要求小明来的时候走过的路径不能包含有1 -> 2 -> 3这部分，但是1 -> 3 或者1 -> 2都是可以的，这样的限制路径可能有多条。

这让小明非常头痛，现在他把问题交给了你。

特别说明，如果1 2 3这三个点共线，但是小明是直接从1到3然后再从3继续，那么此种情况是不认为小明经过了2这个点的。

现在，小明即想走最短的路尽快见到女朋友，又不想打破女朋友的规定，你能帮助小明解决这个问题吗？

Input

输入包含多组样例，每组样例首先包含两个整数n和m，其中n代表有n个点，小明在1号点，女朋友在n号点，m代表小明的女朋友有m个要求；

接下来n行每行输入2个整数x和y（x和y均在int范围），代表这n个点的位置（点的编号从1到n）；

再接着是m个要求，每个要求2行，首先一行是一个k，表示这个要求和k个点有关，然后是顺序给出的k个点编号，代表小明不能走k1 -> k2 -> k3 ……-> ki这个顺序的路径；

n和 m等于0的时候输入结束。

[Technical Specification]

2 <= n <= 50

1 <= m <= 100

2 <= k <= 5

Output

对于每个样例，如果存在满足要求的最短路径，请输出这个最短路径，结果保留两位小数；否则，请输出”Can not be reached!”（引号不用输出）。

Sample Input

3 1

1 1

2 1

3 1

2

1 2

2 1

0 0

1 1

2

1 2

5 3

0 0

5 3

1 2

1 22

5 21

3

1 2 3

2

4 5

2

1 5

0 0

Sample Output

2.00

Can not be reached!

21.65

1003吉哥系列故事——完美队形I

Time Limit: 1.0 Seconds   Memory Limit: 65536K

吉哥这几天对队形比较感兴趣。

有一天，有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] ... h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则称之为完美队形：

1、挑出的人保持他们在原队形的相对顺序不变；

2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然，如果m是奇数，中间那个人可以任意；

3、从左到中间那个人，身高需保证递增，如果用H表示新队形的高度，则H[1] < H[2] < H[3] .... < H[mid]。

现在吉哥想知道：最多能选出多少人组成完美队形？

Input

第一行输入T，表示总共有T组数据(T <= 20)；

每组数据先输入原先队形的人数n(1<=n <= 200)，接下来一行输入n个整数，表示按顺序从左到右原先队形位置站的人的身高（50 <= h <= 250，不排除特别矮小和高大的）。

Output

请输出能组成完美队形的最多人数，每组数据输出占一行。

Sample Input

2

4

1 2 2 1

Sample Output

3

4

1004吉哥系列故事——完美队形II

Time Limit: 1.0 Seconds   Memory Limit: 65536K

吉哥又想出了一个新的完美队形游戏！

假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] ... h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形：

1、挑出的人保持原队形的相对顺序不变，且必须都是在原队形中连续的；

2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然如果m是奇数，中间那个人可以任意；

3、从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H[1] <= H[2] <=  H[3] .... <= H[mid]。

现在吉哥想知道：最多能选出多少人组成新的完美队形呢？

Input

输入数据第一行包含一个整数T，表示总共有T组测试数据(T <= 20)；

每组数据首先是一个整数n(1 <= n <= 100000)，表示原先队形的人数，接下来一行输入n个整数，表示原队形从左到右站的人的身高（50 <= h <= 250，不排除特别矮小和高大的）。

Output

请输出能组成完美队形的最多人数，每组输出占一行。

Sample Input

2

3

1 2 1

4

1 2 2 1

Sample Output

3

4

1005湫湫系列故事——设计风景线

Time Limit: 3 Seconds   Memory Limit: 65536K

随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。

现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？

其中，可以兴建的路线均是双向的，他们之间的长度均大于0。

Input

测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；

接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。

[Technical Specification]

1. n<=100000 

2. m <= 1000000

3. 1<= u, v <= n

4. w <= 1000

Output

对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。

Sample Input

3 3

1 2 1

2 3 1

3 1 1

Sample Output

YES

其中第二题（1002小明系列故事——女友的考验）

源代码为（VC++6.0调试通过）：

#include
#include
#include
#include
//匹配母数组s[]和子数组pa[],匹配则返回1，否则0
int match(int *s,int s_len,int *pa)
{
 int i,j;
    for(i=0,j=0;((i  {
  if(s[i]==pa[j])
  {
   ++i;
   ++j;
  }
  else
  {
   i=i-j+1;
   j=0;
  }
 }
 if((i   return 1;//成功匹配
 else return 0;
}

void main()
{
 int n,m,t,i,j; 
 scanf("%d %d",&n,&m);
   
    while((n!=0)&&(m!=0))
    {
    
  int *x=new int[n];
     int *y=new int[n];
     int **k=new int*[m];
  double dis=-1;

  for(i=0;i   {
   k[i]=new int[n+1];//要多申请一个位，保证“可行解”长度为n时，仍有一位=-1，作为判断标记
   for(j=0;j<=n;j++)
   {    
       k[i][j]=-1;//表明内容无效
    //cout<    }
  }
  
  for(i=0;i   {
            scanf("%d %d",&x[i],&y[i]);   
   //cout<

  }
        //记录约束条件
  for(i=0;i   {

            scanf("%d",&t);
   //cout<    for(j=0;jn位为-1
   { 
    scanf("%d",&k[i][j]);
    k[i][j]-=1;//因为采用数组计数的话从下标0开始，更方便
    //cout<    }

  }
 
  //穷尽每种可行解
        for(i=0;i   {

   int *flag=new int[n];
   flag[0]=flag[n-1]=1;
   for(j=1;j    {
    flag[j]=0;
   }
   int ii=i;
            for(j=1;j    {
    flag[j]=ii%2;
    ii=ii/2;
    if(ii==0)
     break;
   }

   /*cout<<"after flag: ";
            for(j=0;j    {
    cout<    }
            cout<    cout<<"before flag[1]:"<    */

   int *ss=new int[n];//一个可行解
   int a;
   for(j=0,a=0;j    {
    if(flag[j]==1)
    { ss[a]=j;
        a++;
    }
   }

            /*cout<<"ss: ";
   for(j=0;j     cout<    cout<    */
           

   int ff=0;
   for(j=0;j    {
    ff=match(ss,a,k[j]);
       if(ff==1)//满足约束,说明该方案行不通
     break;
   }
   //该方案可行，求出最近一次可行方案中的距离
   if(ff==0)
   {
      double dou,temp=0;
      for(j=0;j       {
      int p=ss[j],q=ss[j+1];
      dou=(x[q]-x[p])*(x[q]-x[p])+(y[q]-y[p])*(y[q]-y[p]);
      temp+=sqrt(dou);
      }
       if((temp       dis=temp;
   }
   
  }//end_of_for();

  if(dis==-1)       
            cout<<"can not be reached!"<   else
   cout<   
  scanf("%d %d",&n,&m);//输入结束
    }
  
}