Well I had this question and i solved it using a computer program and i was wondering could this be done using maths directly as that would run faster(O(1) for those who know time complexity).
Question is as follows:
given n+2 seats and m student.The student must be seated in such a seat so that min(l,r) is maximum where the l and r is the closest distance to nearby occupied seat to the left or right respectively.so print the l and r of the mth student.Previous m-1 students are placed as per the rule that min(l,r) of these students should be maximum.min stands for minimum. Initially first and last seat are occupied already.
Find the l and r of the mth student.
Example: n=7 m=2
Initially: 1 0 0 0 0 0 0 0 1 (1 occupied and 0 empty)
for m=1: 1 0 0 0 1 0 0 0 1 (l=3 and r=3 thats the max value for min(l,r) )
for m=2: 1 0 1 0 1 0 0 0 1 (l=1 and r=1 thats again the max value for min(l,r) )
therefore l=1 and r=1 would have been correct.
my solution in code: https://ideone.com/OefzZG
My idea for a direct solution using my code idea:
well the problem boils down to get to know the highest number of consecutive zero and i know that intially the guy could be either placed on floor(n/2) or ceil(n/2) so i choose any one. therefore i have now 2 sets of 0 sequence floor(n-1/2) and ceil(n-1/2) so i choose the greater one of these 2 and apply same floor and ciel operation and then i take the other one and do so
Illustration : n for m=0 f(n-1/2) c(n-1/2) for m=1 c(c(n-1/2)-1/2) f(c(n-1/2)-1/2) for m=2 c(f(n-1/2)-1/2) f(f(n-1/2)-1/2) for m=3 and so on where f=floor and c=ceil.
Looking for some ideas and concepts on how to deal with this type of question and the mathematical ideas needed.