资料来源:Facebook黑客杯。
我试图从下面的函数中生成一些返回值列表，但似乎找不到找到能够预测 future 随机数的原因。我将如何解决这样的问题？
老虎机黑客
您最近与一个为老虎机编写软件的人成为了 friend 。与他闲逛了一会之后，您会发现他很喜欢炫耀自己对老虎机工作原理的了解。最终，您让他为您详细描述了特定品牌机器上使用的算法。算法如下:
int getRandomNumber(){
secret =( secret * 5402147 + 54321)％10000001;
返回 secret ％1000;
}
此函数返回[0，999]中的整数；每个数字代表在特定机器状态下出现在车轮上的十个符号之一。 secret 最初设置为您不知道的一些非负值。
通过长时间观察机器的运行情况，您可以确定 secret 值，从而预测 future 的结果。了解 future 的结果，您将能够以明智的方式下注并赢得很多钱。
输入
输入的第一行包含正数T，即测试用例的数量。接下来是T测试用例。每个测试用例均包含一个正整数N，即您进行的观察的次数。接下来的N个标记是0到999之间的整数，用于描述您的观察结果。
输出
对于每个测试用例，输出将由机器显示的接下来的10个值，并用空格隔开。
如果您观察到的顺序无法由您的 friend 向您介绍的机器产生，请打印“错误的机器”。
如果您不能唯一确定接下来的10个值，请打印“观察不足”。
约束条件
T = 20
1≤N≤100
输入中的 token 长度不超过3个字符，并且仅包含数字0-9。
样本输入
5
1968
3767308284
5 78 880 53 698 235
7 23 786 292 615 259 635 540
9 862 452 303 558 767 105 911 846 462
样本输出
没有足够的观察
577 428 402 291 252 544 735 545 771 34
762 18 98 703 456 676 621 291 488 332
38802434531725725 86921607 35
机器错误
最佳答案
知道了!
这是我在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个观察就足以确定 future 的结果。
由于在文本编辑器中编写数学内容很麻烦，因此我拍了我的演示解释照片:
关于algorithm - Facebook黑客杯Subround 1B-老虎机黑客，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4812640/