{"raw_statement":[{"iden":"statement","content":"The painting is enclosed in a rock-solid glass chamber that can only be opened with 4 secret codes that need to be entered on 4 different keypads. The head of the museum thinks that this system is unbreakable, and your task is to prove her wrong.\n\nTo help you, a friend reverse-engineered the system. When a code (represented by a positive integer $C$) is entered on a keypad, the keypad sends the $C$-th value produced by a random number generator to a central computer. The central computer only considers the N least significant bits of the 4 pseudo-random values it receives from the 4 keypads. It computes their bitwise XOR (exclusive or) and opens the glass chamber if the result is 0. The pseudo-random number generator is described at the end of the problem statement.\n\nAnother friend found the pseudo-random seeds used by each keypad. With all this information, you think that you can retrieve the 4 secret codes unlocking Mona Lisa.\n\nThe input comprises two lines, each consisting of integers separated with single spaces: \n\n*Limits* \n\nThe output should consist of a single line, whose content is 4 integers, the 4 secret codes, separated with single spaces. Each code must be less than $100000000$. It is guaranteed that at least one solution will exist. Multiple solutions may exist, in which case they will all be accepted.\n\nPseudo-Random Generator The pseudo-random generator is described next in each programming language. You can expect that this pseudo-random generator is not biased in any way.\n\n*C/C++* \n\n*Java* \n\nThe i-th value of the pseudo-random sequence is the result of the i-th application of xoroshiro128plus on 'state'.\n\n*Python 2 / Python 3* \n\n"},{"iden":"input","content":"The input comprises two lines, each consisting of integers separated with single spaces:   The first line contains the integer $N$.  The second line contains the four integer seeds. *Limits*   $1 <= N <= 50$;  each seed is between $0$ and $2^(64) -1$. "},{"iden":"output","content":"The output should consist of a single line, whose content is 4 integers, the 4 secret codes, separated with single spaces. Each code must be less than $100000000$. It is guaranteed that at least one solution will exist. Multiple solutions may exist, in which case they will all be accepted."},{"iden":"note","content":"Pseudo-Random Generator The pseudo-random generator is described next in each programming language. You can expect that this pseudo-random generator is not biased in any way.*C/C++* typedef unsigned long long uint64;uint64 state[2] = { seed, seed ^ 0x7263d9bd8409f526 };uint64 xoroshiro128plus(uint64 s[2]) {  uint64 s0 = s[0];  uint64 s1 = s[1];  uint64 result = s0 + s1;  s1 ^= s0;  s[0] = ((s0 « 55) | (s0 » 9)) ^ s1 ^ (s1 « 14);  s[1] = (s1 « 36) | (s1 » 28);  return result;} The i-th value of the pseudo-random sequence is the result of the i-th application of xoroshiro128plus on 'state'.*Java* long[] state = { seed, seed ^ 0x7263d9bd8409f526L };long xoroshiro128plus(long[] s) {  long s0 = s[0];  long s1 = s[1];  long result = s0 + s1;  s1 ^= s0;  s[0] = ((s0 « 55) | (s0 »> 9)) ^ s1 ^ (s1 « 14);  s[1] = (s1 « 36) | (s1 »> 28);  return result;}The i-th value of the pseudo-random sequence is the result of the i-th application of xoroshiro128plus on 'state'.*Python 2 / Python 3* state = [seed, seed ^ 0x7263d9bd8409f526]def xoroshiro128plus(s):  s0, s1 = s  result = (s0 + s1) % 2**64  s1 ^= s0;  new_state = [(((s0 « 55) | (s0 » 9)) ^ s1 ^ (s1 « 14)) % 2**64,               ((s1 « 36) | (s1 » 28)) % 2**64]  return result, new_state The following loop yields the pseudo-random sequence starting from its first value: while True:  result, state = xoroshiro128plus(state)  yield result"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"Let $ s_1, s_2, s_3, s_4 \\in \\mathbb{N} $ be the known initial seeds for the four keypads.  \nLet $ f: \\mathbb{N} \\to \\mathbb{N} $ be the deterministic function implementing xoroshiro128plus.  \nLet $ v_i(c) = f^c(s_i) $ denote the $ c $-th value generated by keypad $ i $ starting from seed $ s_i $.  \n\nLet $ N \\in \\mathbb{Z}^+ $ be the number of least significant bits considered.  \nLet $ \\text{mask} = 2^N - 1 $.  \n\nDefine $ b_i(c) = v_i(c) \\& \\text{mask} $ as the $ N $-bit truncated value from keypad $ i $ when code $ c $ is entered.  \n\n**Objective**: Find integers $ c_1, c_2, c_3, c_4 \\in \\mathbb{Z}^+ $, each $ < 10^8 $, such that:  \n$$\n(b_1(c_1) \\oplus b_2(c_2) \\oplus b_3(c_3) \\oplus b_4(c_4)) = 0\n$$","simple_statement":"Find 4 positive integers (each < 100000000) such that when each is used as an index to get a value from a shared pseudo-random generator, the XOR of the last N bits of those 4 values equals 0.","has_page_source":false}