首页 > ACM题库 > HDU-杭电 > hdu 1961 Pseudo-random Numbers[解题报告]C++
2013
12-26

hdu 1961 Pseudo-random Numbers[解题报告]C++

Pseudo-random Numbers

问题描述 :

Access to high-quality randomness is very important for many applications, especially in cryptography. Radioactive decay is somtimes used as a source of �rue randomness? but this is a fairly slow procedure for getting random numbers. Also, in many applications it is important that the same �andom?sequence can be produced in two different places. For these reasons one often uses a pseudo-random sequence instead. A pseudo-random sequence is a sequence that is, in fact, not random, but very hard to distinguish from a truly random sequence. A pseudo-random sequence should also be difficult to predict, i.e., given the first few elements of the sequence it should be difficult do determine some later, yet unseen, number in the sequence.

The Association of Cryptographic Machinery (ACM) has devised an algorithm for generating pseudo-random number sequences, but they have no idea how good it really is.Therefore they want you to test it.

The algorithm to generate a sequence of integers, where each integer is between 0 and B − 1 inclusive, is as follows:
1. Start with any number (the seed) in base B. This number can contain hundreds of base B digits.
2. The last digit (least significant) is output as the next element of the sequence.
3. Create a new number by writing down the sum of all neighbouring digits from left to right. E.g., with B = 10, the number 845 would yield the number 129 (since 8 + 4 = 12 and 4 + 5 = 9).
4. Repeat steps 2 and 3 as many times as needed, or until the number has only one base B digit. You get one more pseudo-random digit between 0 and B − 1 each time.

If we have B = 10 and the seed number is 845, then the next numbers will be 129, 311 (1 + 2 = 3, 2 + 9 = 11), 42 (3 + 1 = 4, 1 + 1 = 2), and 6 (4 + 2 = 6). As 6 is a single digit base 10 number, the algorithm terminates. The pseudo-random digits generated are 5, 9, 1, 2 and 6.

You will be testing the generator as follows. You will be given the first L elements output by the generator and an integer T > L. You are supposed to decide if the first T elements are completely determined by the first L elements. To check the robustness of your testing procedure the ACM have slipped in some impossible sequences, i.e. sequences that cannot be generated by any initial seed.

输入:

On the first line of the input is a single positive integer N, telling the number of test cases to follow. The first line of each test case consists of one integer B (2 <= B <= 1 000), the base. The second line consists of an integer L (1 <= L <= 100), followed by the L first elements of some sequence (the elements are written in base 10 and are between 0 and B &#8722; 1 inclusive). The third line consists of an integer T, (L < T <= 100 000), the element of the sequence to predict.

输出:

On the first line of the input is a single positive integer N, telling the number of test cases to follow. The first line of each test case consists of one integer B (2 <= B <= 1 000), the base. The second line consists of an integer L (1 <= L <= 100), followed by the L first elements of some sequence (the elements are written in base 10 and are between 0 and B &#8722; 1 inclusive). The third line consists of an integer T, (L < T <= 100 000), the element of the sequence to predict.

样例输入:

3
10
5 5 9 6 7 0
7
16
4 11 7 8 4
12
2
5 0 1 1 1 0
10

样例输出:

8
unpredictable
impossible

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int N=510;
const int Max=20000;
int n;
double a[N],d[N][N];
bool f[N];

struct point
{
    int x,y;
}p[N];
bool cmp(double x,double y)
{
    return (x>y);
}
double dist(point p1,point p2)
{
    return(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
void path()
{
    int k;
    f[1]=1;
    k=1;
    for(int i=2;i<=n;i++)
    {
        int mcost=Max;
        for(int j=2;j<=n;j++)
        {
            if(!f[j]&&(a[j]<mcost))
            {
                mcost=a[j];
                k=j;
            }
        }
        f[k]=1;
        for(int t=2;t<=n;t++)
        {
            if(!f[t]&&(d[k][t]<a[t]))
            a[t]=d[k][t];
        }
    }
    return;
}
int main()
{
   int test;
   cin>>test;
   while(test--)
   {
       int s;
       cin>>s>>n;
       for(int i=1;i<=n;i++)
       {
           cin>>p[i].x>>p[i].y;
           f[i]=0;
       }
       for(int i=1;i<=n;i++)
       {
           for(int j=i+1;j<=n;j++)
           {
               d[i][j]=dist(p[i],p[j]);
               d[j][i]=d[i][j];
           }
       }
       for(int k=2;k<=n;k++)
       {
           a[k]=d[1][k];
       }
       a[1]=0;
       path();
       sort(a+1,a+n+1,cmp);
       //cout<<a[s+1]<<endl;
       printf("%.2lf\n",a[s]);
   }
    return 0;
}

 

 

解题转自:http://www.cnblogs.com/wuzhibin/archive/2012/02/14/2351380.html


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  3. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  4. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks