CODEWITHSUNDEEP
algorithm
Simon
Simon

Reputation: 2733

Algorithm of choosing the way

I have an interesing problem to share with you. Let's assume you're driving a car and you stumble upon a crossroads with 3 possible ways to choose. You are in need of gas and you need to find a gas station, but there is only one gas station in one of the directions. The task is to find an algorithm of finding the gas station. BUT, assuming x is the distance between the gas station and the crossroads, the total distance you drive has to be a LINEAR function of x.

This has been running my mind for hours now, any ideas? :)

EDIT: You do not know x at the beginning!

Upvotes: 2

Views: 129

Answers (1)

interjay
interjay

Reputation: 110154

Drive 1 km in one direction, then go back. Then drive 2 km in another direction and go back. Then 4, 8, 16, etc. Continue until you find the gas station.

If the gas station was between 2^n and 2^(n+1) km away, you will drive a total of no more than 

S = 2 * (1+2+4+...+2^(n+3)).

So, S < 2 * 2^(n+4) < 32 * 2^n < 32x (because x > 2^n). So will will have driven less than 32x km.

Upvotes: 6

Related Questions