Company: AlgoUniversity_14thjune
Difficulty: medium
This is the hard version of the problem. The only difference from the easy version is that you can ask at most 7 queries. You are given a broken ruler that is missing one number x , where 2 ≤ x ≤ 999 . When the ruler is used to measure a number y , it works as follows: If y < x , it returns the correct length y . If y ≥ x , it returns the incorrect length y + 1 . You don't know what the missing number x is, and you need to find it. To do that, you can make queries of the form ? a b . This means you are measuring the area of a rectangle of size a × b using the broken ruler. The response will be (measured value of a) × (measured value of b) . Your task is to find the missing number x using at most 7 queries. Input Format: There is no initial input. You should begin the interaction by asking a query. Note: Test Case 1: The judge secretly chooses the missing number x = 4 . The solution first requests the area of a 3 × 5 rectangle. Since 3 < x and 5 ≥ x , the measured values are 3 × (