资料来源: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 …
我在考试时得到了以下问题,似乎可能无法实现.有什么我想念的吗？
给定n个对象的数组,只能进行相等性比较,并且对数组中的值范围一无所知,给出一个分而治之的解决方案,用于检测数组中是否存在任何重复项.这必须是O(nlogn)解决方案.
我们可以安全地假设由于问题的性质,解决方案可能与数据结构或基数排序无关,那么这可以就地完成吗？
如果是这样,怎么样？