首页 > ACM题库 > HDU-杭电 > hdu 2322 Random Walking[解题报告]C++
2014
01-05

hdu 2322 Random Walking[解题报告]C++

Random Walking

问题描述 :

The Army of Coin-tossing Monkeys (ACM) is in the business of producing randomness. Good random numbers are important for many applications, such as cryptography, online gambling, randomized algorithms and panic attempts at solutions in the last few seconds of programming competitions.

Recently, one of the best monkeys has had to retire. However, before he left, he invented a new, cheaper way to generate randomness compared to directly using the randomness generated by coin-tossing monkeys. The method starts by taking an undirected graph with 2n nodes labelled 0, 1, …, 2n – 1. To generate k random n-bit numbers, they will let the monkeys toss n coins to decide where on the graph to start. This node number is the first number output. The monkeys will then pick a random edge from this node, and jump to the node that this edge connects to. This new node will be the second random number output. They will then select a random edge from this node (possibly back to the node they arrived from in the last step), follow it and output the number of the node they landed on. This walk will continue until k numbers have been output.

During experiments, the ACM has noticed that different graphs give different output distributions, some of them not very random. So, they have asked for your help testing the graphs to see if the randomness is of good enough quality to sell.

They consider a graph good if, for each of the n bits in each of the k numbers generated, the probability that this bit is output as 1 is greater than 25% and smaller than 75%.

输入:

The input will consist of several data sets. Each set will start with a line consisting of three numbers k, n, e separated by single spaces, where k is the number of n-bit numbers to be generated and e is the number of edges in the graph (1 ≤ k ≤ 100, 1 ≤ n ≤ 10 and 1 ≤ e ≤ 2000). The next e lines will consist of two space-separated integers v1, v2 where 0 ≤ v1, v2 < 2n and v1 ≠ v2. Edges are undirected and each node is guaranteed to have at least one edge. There may be multiple edges between the same pair of nodes.
The last test case will be followed by a line with k = n = e = 0, which should not be processed.

输出:

The input will consist of several data sets. Each set will start with a line consisting of three numbers k, n, e separated by single spaces, where k is the number of n-bit numbers to be generated and e is the number of edges in the graph (1 ≤ k ≤ 100, 1 ≤ n ≤ 10 and 1 ≤ e ≤ 2000). The next e lines will consist of two space-separated integers v1, v2 where 0 ≤ v1, v2 < 2n and v1 ≠ v2. Edges are undirected and each node is guaranteed to have at least one edge. There may be multiple edges between the same pair of nodes.
The last test case will be followed by a line with k = n = e = 0, which should not be processed.

样例输入:

10 2 3
0 3
1 3
2 3
5 2 4
0 1
0 3
1 2
2 3
0 0 0

样例输出:

No
Yes

http://acm.hit.edu.cn/hoj/problem/view?id=2322

一个国际象棋棋盘

挖去两个空

问剩下的为止能否被1×2的矩形填满

 

截一张图

格子黑白相间 相邻两个异色格子正好构成1×2的矩形

因此只要挖去的这两个格子是一黑一白 就一定能被1×2的矩形填满

最后要注意格式

#include <stdio.h>

bool black_white(int x, int y);

int main()
{
    int k, i, a, b, c, d, t;

    scanf("%d", &k);
    for (i = 1; i <= k; i++)
    {
        scanf("%d %d %d %d", &a, &b, &c, &d);
        if (black_white(a, b) != black_white(c, d) )
            t = 1;
        else
            t = 0;
        printf("Scenario #%d:\n", i);
        printf("%d\n\n", t);
    }
    return 0;
}

bool black_white(int x, int y)
{
    if ((x + y) % 2 == 0)
        return 0;
    return 1;
}

 

 

解题转自:http://blog.csdn.net/epk_lee/article/details/8207675


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }