Classical Hard Guessing Problem

Time limit: 1s Memory limit: 256MB Input: Output:

Mr. COACH\mathbb{Mr. \ COACH} chose a random positive integer xx (1x10181 \le x \le 10^{18}) and wants you to guess it.

Initially, he will tell you the sum of digits of xx. Then, you can ask Mr. COACH\mathbb{Mr. \ COACH} to decrease xx by any positive integer yy. If y>xy > x, you lose. Otherwise, x=xyx = x - y and you will be told the sum of digits of the new number.

Mr. COACH\mathbb{Mr. \ COACH} says that you can ask him to decrease xx at most 128128 times.

Task

You need to implement the function long long guess(int s) that returns the hidden number that was chosen at the beginning, knowing the initial sum of digits.

You can call a function int ask(long long y) that will decrease xx by yy and return the new sum of digits.

Example

  • x=13x=13
  • guess is called with s=4s=4
  • ask(1) returns 33 and now x=12x=12
  • ask(3) returns 99 and now x=9x=9
  • ask(10) will now end the game and you lose

Log in or sign up to be able to send submissions!