2013
11-10

# 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 “true randomness”, but this is a fairly slow procedure for getting random numbers. Also, in many applications it is important that the same “random” 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 - 1 inclusive). The third line consists of an integer T, (L < T <= 100 000), the element of the sequence to predict.

For each test case output, on a line of its own:
• “impossible” if no seed number can produce the given sequence.
• “unpredictable” if there exists a seed number that produces the given sequence but the first T elements are not completely determined by the first L elements.
• The T:th element of the sequence in base 10, otherwise.

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

//* @author:alpc12
/* Sample solution to D - Pseudo random numbers / Mikael Goldmann
* First count backwards to recreate the seed number
* The count forwards to get T:th number. Try using few columns to
* save space.
*/
import java.io.*;
import java.util.*;

class Main
{

int[][] tab;
public static void main(String[] ss) throws IOException
{
stdin = new BufferedReader(rdr);
int n = Integer.parseInt(stdin.readLine());
for (int i = 1; i <= n; ++i)
(new Main()).solve(i);
}

void solve(int casenum)  throws IOException
{
int i,j;

int B = Integer.parseInt(stdin.readLine());
String[] tok =stdin.readLine().split("[ ]+");
int L = Integer.parseInt(tok[0]);
int T = Integer.parseInt(stdin.readLine());
int ncol=5;

int[] vals = new int[L];
for (i=1; i <= L; ++i)
vals[i-1] = Integer.parseInt(tok[i]);
boolean ok=false;
while(!ok) {
ok = true;
try{
ncol *= 2;
tab = newtab(L,ncol);
for (i = 0; i < L; ++i)
tab[i][0] = vals[i];
for(i = L-1; i > 0; --i)
if (! explain(tab,i, ncol, B)) {
System.out.println("impossible");
return;
}
}
catch(ArrayIndexOutOfBoundsException e) {
ok = false;
// Retry, doubling number of columns
}
}
// Now tab[0] contains the seed numbers digits

int ncol1=ncol+1; // One extra column

/* Try finding values on the T:th row
* If we fail and truncated any row, retry using
* twice as many columns
*/
int k;
while (true) {
boolean fullrow = false; // no overflowing row yet
int[][] v = new int[2][ncol1];
for (i = 0; i < ncol; ++i)
v[0][i] = tab[0][i];
for (i = ncol; i < ncol1; ++i)
v[0][i] = -1;

int[] a,b=null;;
int tmp;
ok = true;
for (k = 1; k < T; ++k) {
a = v[1-(k&1)];
b = v[k&1];
for (i = 0; i < ncol1; ++i) b[i] = -1;

for (i = 1, j = 0; j < ncol1 &&  i < ncol1; ++i) {
if (a[i] == -1) break;

tmp = a[i-1]+a[i];
if (tmp < B) b[j++] = tmp;
else {
b[j++] = tmp-B;
if (j < ncol1) b[j++] = 1;
}
}
if (j == ncol1) fullrow=true;
if (b[0] == -1) {
ok = false;
break;
}
}
if (ok) {
System.out.println(b[0]);
return;
}
else if(!fullrow) {
System.out.println("unpredictable");
return;
}
ncol1 *=2;
}
}

int[][] newtab(int r, int c)
{
int[][] t = new int[r][c];
int i,j;
for (i=0; i < r; ++i)
for (j = 0; j < c; ++j)
t[i][j] = -1;
return t;

}

/* explain() computes row (i-1) from row i
* Returns false if impossible. Used to calculate seed
* from the given sequence
*/
boolean explain(int[][] tab, int r, int ncol, int B)
{
int[] s = new int[ncol];
int i,j;
for (i=0; i < ncol; ++i) s[i] = -1;
i=0;
j=1;
int s1,t1;
while (i < ncol && tab[r][i] != -1) {
tab[r-1][j] = (B + tab[r][i] - tab[r-1][j-1]) % B;
s1 = tab[r-1][j] + tab[r-1][j-1];
++i;
++j;

if (s1 >= B) {
if (tab[r][i] != -1 && tab[r][i] != 1) return false;
++i;
}
}
return true;

}

}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。