Facebook Hacker Cup Subround 1B - Slot Machine Hacker

Question

Nguồn: Facebook Hacker Cup.

Tôi đã thử tạo một vài danh sách giá trị trả lại từ hàm bên dưới nhưng dường như không thể tìm thấy điều gì làm cho nó có thể dự đoán số ngẫu nhiên trong tương lai. Làm thế nào tôi sẽ đi về giải quyết một vấn đề như thế này?

Slot Machine Hacker

Bạn vừa kết bạn với một chàng trai người viết phần mềm cho máy khe. Sau khi đi chơi với anh ta một chút, bạn nhận thấy rằng anh ấy có một thiên hướng để thể hiện kiến ​​thức của mình về cách các máy khe cắm hoạt động. Cuối cùng bạn có được anh ta để mô tả cho bạn chi tiết chính xác thuật toán được sử dụng trên một thương hiệu máy cụ thể. Thuật toán như sau:

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

Hàm này trả về một số nguyên trong [0, 999]; mỗi chữ số đại diện cho một trong mười biểu tượng xuất hiện trên bánh xe trong một trạng thái máy cụ thể.secret ban đầu được đặt thành một số giá trị không âm mà bạn không biết.

Bằng cách quan sát hoạt động của máy đủ lâu, bạn có thể xác định giá trị của bí mật và do đó dự đoán kết quả trong tương lai. Biết kết quả trong tương lai bạn sẽ có thể đặt cược một cách thông minh và giành được nhiều tiền.

Nhập Dòng đầu tiên của đầu vào chứa số T dương, số lượng trường hợp thử nghiệm. Tiếp theo là các trường hợp kiểm tra T. Mỗi test bao gồm một số nguyên dương N, số quan sát bạn thực hiện. Các mã thông báo tiếp theo là các số nguyên từ 0 đến 999 mô tả các quan sát của bạn. Đầu ra Đối với mỗi trường hợp thử nghiệm, xuất ra 10 giá trị tiếp theo sẽ được hiển thị bởi máy được phân tách bằng khoảng trắng. Nếu trình tự bạn quan sát không thể được sản xuất bởi máy mà bạn của bạn mô tả cho bạn, hãy in “Máy sai” thay thế. Nếu bạn không thể xác định duy nhất 10 giá trị tiếp theo, thay vào đó hãy in “Không đủ quan sát”.

Ràng buộc T = 20 1 ≤ N ≤ 100 Các đầu vào không dài quá 3 ký tự và chỉ chứa chữ số 0-9.

mẫu đầu vào

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 

đầu ra mẫu

 
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

Got it!

Đây là giải pháp của tôi bằng 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" 

Nó có thể có thể được tối ưu hóa (và làm sạch), nhưng kể từ khi nó chạy trong vòng chưa đầy 30 giây trên 3 năm của tôi máy tính xách tay cũ tôi có lẽ sẽ không bận tâm làm cho nó nhanh hơn ...

chương trình không chấp nhận chính xác các đầu vào tương tự như yêu cầu, đây là làm thế nào để sử dụng nó:

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

như bạn thấy, thường là 3 quan sát là đủ để Det ermine các kết quả trong tương lai.

Vì nó là một nỗi đau để viết những thứ toán học trong một trình soạn thảo văn bản tôi lấy một bức tranh về cuộc biểu tình tôi giải thích:

Answer 2

secret luôn là giữa 0 và 10.000.000 bao gồm do mod bởi 10,000,001 . Các giá trị được quan sát luôn là 3 chữ số cuối cùng của secret (với số 0 đứng đầu) do mod thay đổi 1.000. Vì vậy, đó là các chữ số khác chưa được biết và chỉ để lại cho chúng tôi 10.001 số để lặp lại.

Đối với mỗi prefix bằng 0.10.000, chúng tôi bắt đầu bằng secret được xây dựng từ các số của prefix tiếp theo là số đầu tiên trong chuỗi được quan sát có số 0 đứng đầu. Nếu danh sách các số được tạo bằng với danh sách được quan sát, chúng ta có một hạt giống tiềm năng. Nếu chúng ta kết thúc mà không có hạt giống tiềm năng, chúng ta biết điều này phải là một cỗ máy sai. Nếu chúng ta kết thúc với nhiều hơn một, chúng ta không có đủ quan sát. Nếu không, chúng tôi tạo ra 10 giá trị tiếp theo bằng cách sử dụng hạt giống duy nhất.

Điều này chạy bằng O (10.000NT), là O (20.000.000) cho các ràng buộc được đưa ra. Dưới đây là một giải nén từ giải pháp của tôi trong C++ (lý do sử dụng nhiều macro, tôi chỉ sử dụng chúng trong các cuộc thi):

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

Điều gì được biết ở đây? Công thức cập nhật bí mật và danh sách các quan sát. không xác định là gì? Giá trị bí mật bắt đầu.

Bí mật bắt đầu có thể là gì? Chúng tôi có thể giới hạn bí mật có thể bắt đầu từ đến 10.000 giá trị có thể, vì giá trị được quan sát là secret % 1000 và bí mật tối đa là 10.000.000.

Những bí mật khởi đầu có thể là sau đó

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

Chỉ có một tập hợp con (nếu có) của những bí mật sẽ cập nhật một giá trị đó sẽ hiển thị giá trị quan sát tiếp theo.

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] 

Ngay cả khi tất cả các giá trị possible vẫn còn trong new_possible, chúng tôi sẽ chỉ được kiểm tra 10.000 số cho mỗi quan sát. Tuy nhiên, không có khả năng nhiều giá trị sẽ khớp với hơn nhiều quan sát.

Chỉ cần tiếp tục lặp lại quy trình đó và danh sách có thể sẽ trống, dài hơn một, hoặc nó sẽ có chính xác một câu trả lời.

Đây là một chức năng để ghép tất cả lại với nhau. (bạn cần số f từ trên cao)

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