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

Question

资料来源:Facebook黑客杯.

我已经尝试从下面的函数生成一些返回值列表,但似乎无法找到可以预测未来随机数的原因.我将如何解决像这样的问题？

老虎机黑客

您最近结识了一位为老虎机编写软件的人.和他一起闲逛之后,你会注意到他喜欢炫耀他对老虎机如何工作的了解.最后,让他让您详细描述特定品牌机器上使用的算法.算法如下:

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

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

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

输入输入的第一行包含正数T,测试用例数.接下来是T测试用例.每个测试用例都包含一个正整数N,即你所做观察的数量.接下来的N个标记是从0到999的整数,用于描述您的观察结果.输出对于每个测试用例,输出由空格分隔的机器显示的下10个值.如果您的朋友描述的机器无法生成您观察到的序列,请打印"错误的机器".如果您无法唯一确定接下来的10个值,请打印"不够观察".

约束条件T = 201≤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"

它可能会被优化(和清理),但由于它在我3岁的笔记本电脑上运行不到30秒,我可能不会打扰它让它更快...

程序不接受与请求完全相同的输入,以下是如何使用它:

>>> 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个观察值足以确定未来的结果.

由于在文本编辑器中编写数学内容很痛苦,因此我拍摄了我的演示说明: