LCC '18 Contest 1 S4 - Birthday Problem

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Alice and Bob are in charge of planning Eve’s surprise birthday party. Since Eve is known for listening in on her friends’ conversations, Alice and Bob have devised a plan to establish a secure communication channel. Alice will send Bob a list of 50\ 000 random integers in the range [0, 2^{31} - 1] encoded using the following function:

\displaystyle f(n) = 1103515245*n + 12345 \bmod 2^{31}

(This function maps each integer in the range [0, 2^{31}-1] to a unique integer in the same range).

Bob’s task is to determine one of the original integers that Alice chose, in which case they can use that number as their secret key. However, Bob forgot how he can find one of the original numbers that Alice sent him. Can you help him find such a number?

Input Specification

The first line of input contains an integer N (N = 50\ 000). The next line contains N integers, the encodings of the integers that Alice chose using the function f(n).

Output Specification

One of Alice's original integers.

Sample Input 1 (Note N < 50 000)


Sample Output 1


Sample Input 2 (Note N < 50 000)

1341714958 297746555 1401261800 357293397

Sample Output 2


Explanation of Sample Input

Note that the sample input has less than 50\ 000 integers, while the real input will have exactly 50\ 000 integers. In the first case, the original number is 2018. In the second case, the original numbers are 9, 10, 11, 12. Any of these is a correct output.


There are no comments at the moment.