Hello everybody,

Recently I participated in day 1 of CEOI unofficially online (invitation-only) and even though I performed poorly, after the competition we discussed the solutions of all problems. Except one. Here is the problem, any ideas would be very helpful! I will also include the results we found while trying to solve it below. Here is the problem, shortened because the real statement was quite long. I also changed a little bit the idea of the way of the testing to make it more clear, since what matters is the idea.

A and B want to break into a top-secret laboratory. The security system asks a question. The question 1<=q<=N is represented by a number. They are sure that the question the system will ask will be x or y. The answer to question x is "yes" and the answer to question y is "no". When the question was asked, A and B were separated, and unfortunately only A remembered the questions x and y, while B was the one next to the door ready to answer. Now A must shout exactly one number h (1<=h) and encode in it all the information B needs to answer the question. Help them by writing the following two programs :

1) for given values N,x,y return a number h that is the number A shouted.

2) for given values N,q,h return true for "yes" or false for "no", if q is the question and h is the number A shouted to B.

The second program will always receive an h that was produced by your first program.

Score is as follows : for h>=21 — 0 points

for h=20 — 27 points

for h=19 — 30 points

for h=18 — 33 points

for h=17 — 37 points

for h=16 — 42 points

for h=15 — 50 points

for h=14 — 60 points

for h=13 — 75 points

for h<=12 — 100 points

where h is the largest value your first program produced in any of the tests.

Constraints : 1<=N<=920 and your program can be run on 2,000,000 tests (all possible inputs, obviously).

Time Limit : 7s Memory Limit : 256MB

Example

The first program encode(N,x,y) was called a few times, and returns the following values:

encode(5,1,2) = 12

encode(5,4,5) = 2

encode(5,1,2) = 12

encode(5,3,5) = 4

encode(5,4,5) = 2

encode(5,5,2) = 1

Then the second function decode(N,q,h) should return :

decode(5,1,12) = true

decode(5,4,2) = true

decode(5,2,12) = false

decode(5,3,4) = true

decode(5,5,2) = false

decode(5,2,1) = false

During the compeition almost all of us found a solution for h=20, I managed to solve it for h=16 and Hristo Venev managed to get h=14. However none of us managed to get any idea for h=13 or full score. Any ideas will be appreciated!

Thanks in advance !