Facebook Hacker Cup Subround 1B - Хакер игровых автоматов

Question

Источник: Facebook Hacker Cup.

Я попытался сгенерировать несколько списков возвращаемых значений из функции ниже, но, похоже, не могу найти то, что позволяет предсказывать будущие случайные числа.Как мне решить проблему, подобную этой?

Хакер игровых автоматов

Вы недавно подружились с парнем, который пишет программное обеспечение для игровых автоматов.Немного пообщавшись с ним, вы замечаете, что у него есть склонность демонстрировать свои знания о работе игровых автоматов.В конце концов вы заставляете его точно описать для вас алгоритм, используемый на машине определенной марки.Алгоритм выглядит следующим образом:

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

Эта функция возвращает целое число в [0, 999];каждая цифра представляет собой один из десяти символов, которые появляются на колесе во время определенного состояния машины. Первоначально для secret установлено некое неотрицательное значение, неизвестное вам.

Наблюдая за работой машины достаточно долго, вы можете определить значениесекрет и, таким образом, прогнозировать будущие результаты.Зная будущие результаты, вы сможете делать умные ставки и выигрывать много денег.

Входные данные В первой строке входных данных содержится положительное число 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 наблюдений, чтобы определить будущие результаты.

Поскольку писать текст по математике в текстовом редакторе довольно сложно, я сфотографировал свое объяснение 1014 *:

Answer 2

Что здесь известно? Формула обновления секрета и список наблюдений. Что такое неизвестно? Начальное секретное значение.

Каким может быть начальный секрет? Мы можем ограничить возможный старт секрет 10 000 возможных значений, поскольку наблюдаемое значение равно secret % 1000, а максимальный секрет составляет 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, мы бы проверяли только 10 000 цифры для каждого наблюдения. Но вряд ли многие значения будут совпадать несколько наблюдений.

Просто продолжайте итерацию этого процесса, и любой из возможных списков будет пустым, длиннее одного, или у него будет ровно один ответ.

Вот функция, чтобы собрать все это вместе. (вам нужно 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()

Answer 3

secret всегда между 0 и 10 000 000 включительно из-за мода на 10 000 001.Наблюдаемые значения всегда являются последними 3 цифрами secret (с удалением ведущих нулей) из-за мода на 1000.Так что остальные цифры неизвестны, и нам остается только 10 001 цифр для повторения.

Для каждого prefix в 0..10,000 мы начинаем с secret, построенного из цифр prefix с последующим первым числом в наблюдаемой последовательности с ведущими нулями.Если список сгенерированных чисел равен наблюдаемому списку, у нас есть потенциальное начальное число.Если у нас нет потенциальных семян, мы знаем, что это неправильная машина.Если мы заканчиваем более чем одним, у нас недостаточно наблюдений.В противном случае мы генерируем следующие 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;
}