StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What is known here? The formula for updating the secret, and the list of observations. What is unknown? The starting secret value. </p> <p>What could the starting secret be? We can limit the possible starting secret to 10,000 possible values, since the observed value is <code>secret % 1000</code>, and the maximum secret is 10,000,000.</p> <p>The possible starting secrets are then </p> <pre><code>possible = [1000 * x + observed for x in xrange(10001)] </code></pre> <p>Only a subset (if any) of those secrets will update to a value that will show the next observed value.</p> <pre><code>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] </code></pre> <p>Even if every <code>possible</code> value was still in <code>new_possible</code>, we would only be checking 10,000 numbers for every observation. But, it is not likely that many values will match over multiple observations.</p> <p>Just keep iterating that process, and either the possible list will be empty, longer than one, or it will have exactly one answer.</p> <p>Here is a function to put it all together. (you need the <code>f</code> from above)</p> <pre><code>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() </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload