ADV04J - Invisible point

no tags 

Daniel marked a point on a plane with sympathetic ink and he has also drawn a regular n-gon with normal ink. Max can see the n-gon, but can't see the point. Max can draw a line and ask Daniel which side of the line the point is. What is the minimum number of questions Max have to ask to define if the point is inside the n-gon in the worst case?


First line of the input contains number t - the amount of test cases. Each test consists of the single integer n - the amount of sides of the n-gon.


1 <= t <= 100
3 <= n <= 1000000


For each test case print a single number - the answer to the question in the statement.




hide comments
mahabir10: 2020-09-21 07:20:03

Extremely easy

tarun_28: 2019-12-09 11:25:23

watch out when n is odd..

mittalprateek: 2018-10-16 21:02:36

just observe the pattern..simple maths only ..

oneinchatatime: 2018-07-18 14:29:05

very nice problem

mag1x_: 2018-05-30 18:25:40

my 50th simple maths :)

Rakend Chauhan: 2017-01-01 07:31:00

the question is DP XD

ace_cocytus: 2016-10-05 16:11:21

If Im not wrong, test case 4 (a rectangular); draw diagonally to find which side the point is. And then, we can draw the next 2 lines based on side the point is, to get the answer (the point inside the n-gon or not).

kataria: 2016-07-31 09:22:21

nice prob.

minhthai: 2016-01-25 05:49:31

ask your friends: pen and paper :)

anuveshkothari: 2015-08-14 15:26:24

@rishabh comment helps in finding the approach of the problem

Added by:Spooky
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Advancement Autumn 2010,