Facebook黑客杯子Subround 1B - 老虎机黑客

Question

来源：Facebook黑客杯。

我试过从下面的函数生成一些返回值的列表，但似乎无法找到能够预测未来随机数的原因。我将如何去解决像这样的问题？

老虎机黑客

您最近结识了一个人谁老虎机编写软件。在和他聊了一会儿之后，你会注意到他喜欢展示他对老虎机的工作方式的了解。最终，你会让他详细描述特定品牌机器上使用的算法。该算法如下：

 
int getRandomNumber() { 
    secret = (secret * 5402147 + 54321) % 10000001; 
    return secret % 1000; 
} 

该函数返回[0，999]中的整数值;每个数字表示在特定机器状态期间出现在车轮上的十个符号之一.secret最初设置为您未知的某个非负值。

通过观察足够长的机器的运行情况，您可以确定机密值，从而预测未来结果。了解未来的结果，您将能够以聪明的方式下注并赢得大量资金。

输入 输入的第一行包含正数T（测试用例的数量）。随后是T测试用例。每个测试用例都包含一个正整数N，即您所做的观察次数。接下来N个令牌是从0到999的整数，用于描述您的观察结果。 输出 对于每个测试用例，输出将由机器显示的下一个10个值，用空格分隔。 如果您观察到的序列不能由朋友向您描述的机器生成，请打印“错误的机器”。 如果您无法唯一确定接下来的10个值，请输入“没有足够的观察值”。

约束 T = 20 1≤N≤100个 令牌在输入是不超过3个字符，并且仅包含数字0-9。

样品输入

5 
1 968 
3 767 308 284 
5 78 880 53 698 235 
7 23 786 292 615 259 635 540 
9 862 452 303 558 767 105 911 846 462 

样本输出

 
Not enough observations 
577 428 402 291 252 544 735 545 771 34 
762 18 98 703 456 676 621 291 488 332 
38 802 434 531 725 594 86 921 607 35 
Wrong machine 

Answer 1

明白了！

这是我在Python的解决方案：

a = 5402147 
b = 54321 
n = 10000001 

def psi(x): 
    return (a * x + b) % n 

inverse1000 = 9990001 
max_k = (n-1)/1000 + 1 

def first_input(y): 
    global last_input, i, possible_k 
    last_input = y 
    possible_k = [set(range(max_k))] 
    i = 0 

def add_input(y): 
    global last_input, i 
    c = inverse1000 * (b + a * last_input - y) % n 
    sk0 = set() 
    sk1 = set() 
    for k0 in possible_k[i]: 
     ak0 = a * k0 % n 
     for k1 in range(max_k): 
      if (k1 - ak0) % n == c: 
       sk0.add(k0) 
       sk1.add(k1) 
       #print "found a solution" 
    last_input = y 
    possible_k[i] = possible_k[i] & sk0 
    possible_k.append(sk1) 
    i += 1 
    if len(possible_k[i-1]) == 0 or len(possible_k[i]) == 0: 
     print "Wrong machine" 
     return 
    if len(possible_k[i]) == 1: 
     x = y + 1000 * possible_k[i].copy().pop() 
     for j in range(10): 
      x = psi(x) 
      print x % 1000, 
     print 
     return 
    print "Not enough observations" 

这也许可以优化（和清理），但由于它在不到30秒运行在我3岁的笔记本电脑，我可能不会打扰使它快...

程序并不完全接受相同的输入的要求，这里是如何使用它：

>>> first_input(767) 
>>> add_input(308) 
Not enough observations 
>>> add_input(284) 
577 428 402 291 252 544 735 545 771 34 

>>> first_input(78) 
>>> add_input(880) 
Not enough observations 
>>> add_input(53) 
698 235 762 18 98 703 456 676 621 291 
>>> add_input(698) 
235 762 18 98 703 456 676 621 291 488 
>>> add_input(235) 
762 18 98 703 456 676 621 291 488 332 

>>> first_input(862) 
>>> add_input(452) 
Not enough observations 
>>> add_input(303) 
Wrong machine 
>>> add_input(558) 
Wrong machine 

正如你所看到的，通常是3周的观察是不够DET呃未来的结果。

由于这是一个痛苦写数学的东西，在一个文本编辑器，我把我的 演示的图片 解释：

Answer 2

secret始终是0和10,000,000（含）之间由于10000001国防部。观察到的值始终是secret的最后3位数字（前导零被剥离），因为mod为1,000。所以这是其他数字是未知的，只剩下10,001个数字来迭代。

对于0..10,000中的每个prefix，我们以从prefix的数字构成的secret开始，后面跟着具有前导零的观察序列中的第一个数字。如果生成的数字列表等于观察列表，我们有潜在的种子。如果我们没有潜在的种子，我们知道这肯定是一个错误的机器。如果我们以多于一个结束，我们没有足够的观察。否则，我们使用单个种子生成接下来的10个值。

这运行在O（10,000NT），对于给定的约束，它是O（20,000,000）。下面是我在C++解决方案的提取物（原谅大量使用宏，我只使用他们在比赛中）：

int N; 
cin >> N; 
int n[N]; 
REP(i, N) 
    cin >> n[i]; 
ll poss = 0, seed = -1; 
FOR(prefix, 0, 10001) { 
    ll num = prefix * 1000 + n[0]; 
    bool ok = true; 
    FOR(i, 1, N) { 
    ll next = getRandomNumber(num); 
    if (next != n[i]) { 
     ok = false; 
     break; 
    } 
    } 
    if (ok) { 
    poss++; 
    seed = prefix * 1000 + n[0]; 
    } 
} 
if (poss == 0) { 
    cout << "Wrong machine" << endl; 
} else if (poss > 1) { 
    cout << "Not enough observations" << endl; 
} else { 
    ll num = seed; 
    FOR(i, 1, N) 
    getRandomNumber(num); 
    REP(i, 10) 
    cout << getRandomNumber(num) << " "; 
    cout << endl; 
} 

Answer 3

这到底是怎么知道的？更新秘密的公式和观察列表。什么是 未知？开始的秘密价值。

最初的秘密是什么？由于观察值为secret % 1000，我们可以将可能的起始密码限制为10,000个可能的值，最大密码为10,000,000。

可能的起始秘密然后

possible = [1000 * x + observed for x in xrange(10001)] 

只有一个子集（如果有的话）的那些秘密将更新，以将显示下一个 观测值的值。

def f(secret): 
    return (secret * 5402147 + 54321) % 10000001 

# obs is the second observation. 
new_possible = [f(x) for x in possible] 
new_possible = [x for x in new_possible if x % 1000 == obs] 

即使每possible值仍然是在new_possible，我们将只检查每个观测万个 号码。但是，很多值不可能与多个观测结果相匹配。

只是继续迭代该过程，并且可能的列表将是空的，比一个长， 或者它将只有一个答案。

这是一个把它放在一起的功能。 （你需要从上面的f）

def go(observations): 
    if not observations: 
     return "not enough observations" 

    # possible is the set of all possible secret states. 
    possible = [x * 1000 + observations[0] for x in xrange(10001)] 

    # for each observation after the first, cull the list of possible 
    # secret states. 
    for obs in observations[1:]: 
     possible = [f(x) for x in possible] 
     possible = [x for x in possible if x % 1000 == obs] 
     # uncomment to see the possible states as the function works 
     # print possible 

    # Either there is 0, 1, or many possible states at the end. 
    if not possible: 
     return "wrong machine" 
    if len(possible) > 1: 
     return "not enough observations" 

    secret = possible[0] 
    nums = [] 
    for k in xrange(10): 
     secret = f(secret) 
     nums.append(str(secret % 1000)) 
    return " ".join(nums) 

import sys 

def main(): 
    num_cases = int(sys.stdin.readline()) 

    for k in xrange(num_cases): 
     line = [int(x) for x in sys.stdin.readline().split()] 
     print go(line[1:]) 

main()