首页 > ACM题库 > HDU-杭电 > hdu 3393 Precious待解决[解题报告]C++
2014
03-23

hdu 3393 Precious待解决[解题报告]C++

Precious

问题描述 :

Gollum is finding his Precious. The precious is hiding in a magic maze. The maze can be considered as a simple polygon. Some vertexes of the polygon are doors that can only allow Gollum to get in, and the other doors can only allow Gollum to get out.
Gollum doesn’t know that restrict, he choose a door to get in, and choose a door to get out after he has got his precious. Gollum hasn’t learned math, so we believe that Gollum choose the door randomly, that means if there are n doors, the probability of a door chose by Gollum is 1/n.
There is a monster in the maze, and if Gollum stay in the maze more than m minutes, the monster will wake up and eat Gollum. Gollum can move one unit distance by one minute.
We want to know the probability that Gollum got his precious.

输入:

The input consists of multiply test cases. The first line of each test case contains two integers, n (3 <= n <= 100), m (0 <= m <= 10000), where n is the number of vertexes of the maze, and m is the time limit. The next n lines represent the maze, each line contains a coordinate, x, y (-10000 <= x, y <= 10000) and a DoorType. If DoorType equals to -1, then you can get in from this vertex; if DoorType equals to 0, then it’s not a door; if DoorType equals to 1, then you can get out from this vertex. The last line of each test case is a coordinate, indicating the location of the precious. You can assume that the precious is always in the maze.
The last test case is followed by a line containing two zeros, which means the end of the input.

输出:

The input consists of multiply test cases. The first line of each test case contains two integers, n (3 <= n <= 100), m (0 <= m <= 10000), where n is the number of vertexes of the maze, and m is the time limit. The next n lines represent the maze, each line contains a coordinate, x, y (-10000 <= x, y <= 10000) and a DoorType. If DoorType equals to -1, then you can get in from this vertex; if DoorType equals to 0, then it’s not a door; if DoorType equals to 1, then you can get out from this vertex. The last line of each test case is a coordinate, indicating the location of the precious. You can assume that the precious is always in the maze.
The last test case is followed by a line containing two zeros, which means the end of the input.

样例输入:

12 4
-2 -1 -1
-1 -1 -1
-1 -2 -1
1 -2 -1
1 -1 -1
2 -1 -1
2 1 1
1 1 1
1 2 1
-1 2 1
-1 1 1
-2 1 1
0 0
0 0

样例输出:

0.138888889


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }