Hunt the Rabbit
InterviewTime limit2sMemory limit512 MB
For each hidden rabbit position, print the sequence of envelope numbers a lower-middle binary search opens until it finds the rabbit.
- Level
Easy3 of 10
- Topics
- Binary search, Simulation
- Solved
- No attempts yet
Problem
Mr Farkle grew up on a farm and spent a good part of his youth hunting rabbits. He now teaches maths and computing, and he invented a hunting game that teaches his students the binary search.
He lines up 50 envelopes at the front of the room, numbered 1 to 50 in order. In one of them he hides a rabbit, which is only a card with a picture of a rabbit on it. Every other envelope holds a card too. If an envelope has a number lower than the envelope with the rabbit, its card reads "Try a higher number". Otherwise the card reads "Try a lower number".
A student has to find the rabbit with a binary search and write down the numbers of all the envelopes opened, in the order they were opened. In a binary search the student opens the middle envelope of the range still being searched. The middle is easy to find when the range holds an odd number of envelopes, but when it holds an even number, the student has to open the lower numbered of the two middle envelopes. So the first envelope opened is always 25.
Input
Each line holds one integer between 1 and 50 inclusive, the number of the envelope where Mr Farkle hid the rabbit. The last line holds 0 and is not processed.
Output
For each input line, print the numbers of all the envelopes opened, in the order they were opened, up to and including the envelope that holds the rabbit. Print them on one line, separated by a single space.