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()