Keep talking and nobody explodes – medium
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You have the safe lock which consists of 5 decimal digits. If you rotate some digit, it increases by one, except 9 which becomes 0.

Initially, the lock contains number $$$x$$$. To unlock the safe you must do the following operations in order (and be careful, don't mix up if and else statements).

If sum of digits on positions 3 and 4 is greater than 10, rotate digit on position 2 by 9 times, else rotate digit on position 5 by 4 times.

If digit on position 3 is greater than digit on position 5, rotate digit on position 2 by 4 times, else rotate digit on position 4 by 6 times.

If digit on position 5 is greater than digit on position 3, rotate digit on position 2 by 1 times, else rotate digit on position 1 by 7 times.

If sum of digits on positions 4 and 1 is greater than 8, rotate digit on position 2 by 7 times, else rotate digit on position 3 by 3 times.

If digit on position 4 is greater than digit on position 1, rotate digit on position 2 by 3 times, else rotate digit on position 3 by 2 times.

If sum of digits on positions 1 and 2 is greater than 9, rotate digit on position 3 by 6 times, else rotate digit on position 5 by 3 times.

If digit on position 3 is greater than digit on position 2, rotate digit on position 1 by 2 times, else rotate digit on position 4 by 5 times.

If digit on position 5 is greater than digit on position 3, rotate digit on position 2 by 1 times, else rotate digit on position 4 by 5 times.

If sum of digits on positions 5 and 1 is greater than 10, rotate digit on position 4 by 7 times, else rotate digit on position 3 by 5 times.

If sum of digits on positions 5 and 4 is greater than 9, rotate digit on position 3 by 9 times, else rotate digit on position 2 by 4 times.

If sum of digits on positions 3 and 1 is greater than 8, rotate digit on position 2 by 8 times, else rotate digit on position 4 by 4 times.

If digit on position 5 is greater than digit on position 2, rotate digit on position 1 by 5 times, else rotate digit on position 3 by 8 times.

If sum of digits on positions 1 and 4 is greater than 10, rotate digit on position 3 by 4 times, else rotate digit on position 5 by 1 times.

If digit on position 3 is greater than digit on position 5, rotate digit on position 2 by 1 times, else rotate digit on position 1 by 6 times.

If sum of digits on positions 1 and 5 is greater than 9, rotate digit on position 3 by 3 times, else rotate digit on position 2 by 1 times.

If digit on position 5 is greater than digit on position 1, rotate digit on position 4 by 8 times, else rotate digit on position 2 by 1 times.

If digit on position 4 is greater than digit on position 1, rotate digit on position 3 by 4 times, else rotate digit on position 5 by 4 times.

If sum of digits on positions 3 and 1 is greater than 8, rotate digit on position 5 by 3 times, else rotate digit on position 2 by 6 times.

If digit on position 3 is greater than digit on position 4, rotate digit on position 2 by 3 times, else rotate digit on position 1 by 5 times.

If digit on position 5 is greater than digit on position 4, rotate digit on position 2 by 7 times, else rotate digit on position 3 by 8 times.

If digit on position 2 is greater than digit on position 4, rotate digit on position 5 by 9 times, else rotate digit on position 1 by 4 times.

If sum of digits on positions 3 and 5 is greater than 10, rotate digit on position 4 by 1 times, else rotate digit on position 2 by 5 times.

If digit on position 4 is greater than digit on position 1, rotate digit on position 3 by 9 times, else rotate digit on position 2 by 9 times.

If digit on position 5 is greater than digit on position 3, rotate digit on position 2 by 4 times, else rotate digit on position 1 by 6 times.

If sum of digits on positions 3 and 4 is greater than 9, rotate digit on position 5 by 8 times, else rotate digit on position 2 by 5 times.

If sum of digits on positions 3 and 4 is greater than 10, rotate digit on position 5 by 2 times, else rotate digit on position 1 by 5 times.

If sum of digits on positions 5 and 4 is greater than 9, rotate digit on position 3 by 3 times, else rotate digit on position 1 by 8 times.

If digit on position 5 is greater than digit on position 2, rotate digit on position 1 by 4 times, else rotate digit on position 3 by 8 times.

If digit on position 3 is greater than digit on position 1, rotate digit on position 5 by 6 times, else rotate digit on position 2 by 6 times.

If digit on position 4 is greater than digit on position 5, rotate digit on position 1 by 6 times, else rotate digit on position 3 by 1 times.

If sum of digits on positions 3 and 5 is greater than 10, rotate digit on position 2 by 5 times, else rotate digit on position 1 by 7 times.

If sum of digits on positions 5 and 2 is greater than 9, rotate digit on position 4 by 9 times, else rotate digit on position 3 by 5 times.

If sum of digits on positions 2 and 4 is greater than 10, rotate digit on position 3 by 1 times, else rotate digit on position 1 by 2 times.

If digit on position 3 is greater than digit on position 4, rotate digit on position 5 by 7 times, else rotate digit on position 2 by 1 times.

If digit on position 2 is greater than digit on position 5, rotate digit on position 1 by 6 times, else rotate digit on position 4 by 2 times.

If digit on position 2 is greater than digit on position 1, rotate digit on position 5 by 3 times, else rotate digit on position 4 by 4 times.

If digit on position 5 is greater than digit on position 4, rotate digit on position 3 by 9 times, else rotate digit on position 1 by 9 times.

If digit on position 1 is greater than digit on position 5, rotate digit on position 4 by 6 times, else rotate digit on position 2 by 5 times.

If sum of digits on positions 1 and 5 is greater than 10, rotate digit on position 3 by 7 times, else rotate digit on position 2 by 4 times.

If sum of digits on positions 2 and 1 is greater than 9, rotate digit on position 3 by 7 times, else rotate digit on position 5 by 4 times.

Input format:
Input contains single number $$$x$$$ consisting of exactly 5 digits, leading zeroes are allowed.

Output format:
Output the number after applying all operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
00000

Example output:
43266

Example input:
12345

Example output:
87229

Editorial:
Here bruteforce takes way too long to finish, so the idea here is meet-in-the-middle: all operations are reversible, so if we iterate over all first-25-mix-up-masks and last-25-mix-up-masks, we can sort the obtained middle images and use a two-pointers technique to get the intersection. It may turn out that one test is not enough here (maybe because of somewhat similar to the birthdays paradox), so one should do mitm for a pair of tests, not for a single one.