Editorial for TLE '17 Contest 5 P1 - Guess the Number - Olympiads Online Judge

Editorial for TLE '17 Contest 5 P1 - Guess the Number

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

There are several guessing strategies, and points were awarded based off of how many guesses.

For $10\%$ ~10\%~ of the points, we make more than $110$ ~110~ guesses. This could be achieved by making random guesses and stopping once we guess the correct answer.

For $20\%$ ~20\%~ of the points, we make more than $50$ ~50~ guesses. This could be achieved by guessing each number from $-50$ ~-50~ to $50$ ~50~.

For $30\%$ ~30\%~ of the points, we make more than $10$ ~10~ guesses. This could be achieved by guessing numbers from $-50$ ~-50~ to $50$ ~50~ at a certain interval, (say, $-50, -45, \dots, 45, 50$ ~-50, -45, \dots, 45, 50~) and checking individual numbers when close.

For $50\%$ ~50\%~ of the points, we make more than $3$ ~3~ guesses. This could be achieved by performing a binary search.

For $75\%$ ~75\%~ of the points, we make $2$ ~2~ guesses. This could be achieved by guessing $0$ ~0~ and knowing that $N$ ~N~ could either be $|N-0|$ ~|N-0|~ or $-|N-0|$ ~-|N-0|~.

For $100\%$ ~100\%~ of the points, we make $1$ ~1~ guess. We note that if we guess $50$ ~50~, then the answer must be $50-|N-50|$ ~50-|N-50|~, since the answer cannot be more than $50$ ~50~. We could have done the same with $-50$ ~-50~ instead.

Time Complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Comments

There are no comments at the moment.