CareerCup

class Lane;
class Car;

class Frog
{
public:
	int lane; // index into lane array
	int pos; // initial position of frog, note the pos does not change only lane changes but we need initial p
			  // position to know at what location in a lane are we jumping.
	long long time;     // the time, initial value is 0;
public:
	Frog(unsigned int p)
	{
		lane = -1;
		pos = p;
		time = 0;
	}

	Jump()
	{
		lane++;
	}
	Wait()
	{
		time++;
	}
};

class Car
{
public:
	int length;
	int startPos;

public:
	int GetPosition(long long time, unsigned int speed); // returns position of front bonet
};

class Lane
{
public:
	Car *cars; // all the cars in lane
	int ncar; // number of cars;
	unsigned int speed; // the speed of the lane

public:
	bool IsLaneClear(long long t,  int pos); // returns true if lane is clear at time t, at position pos
};

bool CrossLanes(Frog frog, long long MaxTime, Lane *lanes, int nLane)
{
	if (frog.lane == nLane)
		return true;
	if (frog.time >= MAX_TIME)
		return false;

	Lane *lane;
	while (frog.time < MAX_TIME)
	{
		if (frog.lane >= 0)
		{
			lane = lanes[frog.lane];	
			if (! (lane->IsLaneClear(frog.time, frog.pos)))
			{	
				return false;
			}
			else
			{
				// check the next lane for free
				lane = lanes[front.lane+1];
				if (lane->isLaneClear(frog.time+1, frog.pos))
				{
					frog.lane++;
					frog.time++;
					bool bcrossed = CrossLanes(frog, MAX_TIME, lanes, nLane);
					if (bcrossed == false)
					{
						frog.lane--;
						frog.time--;
					}
					else
					{
						return true;
					}
				}
				frog.Wait();
			}
		}
		else
		{
			lane = lanes[0];
			if (lane->IsLaneClear(frog.time, frog.pos))
			{
				frog.lane++;
				frog.time++;
				bool bcrossed = CrossLanes(frog, MAX_TIME, lanes, nLane);
				if (bcrossed == false)
				{
					frog.lane--;
					frog.time--;
				}
				else
				{
					return true;
				}
			}
			frog.Wait();
		}
	}
	// time out
	return false;
}

You need some time limit in here. If you know that car pattern repeats in T seconds then you can choose T as your time.

Consider this problem as follows: can frog reach the other side in T seconds? At any point of time frog's state can be desribed as (lane, time) in [0..N+1, 0..T] (lane=0 is your initial lane, lane=N+1 is your destination). Your initial point is (0,0). Use BFS to find the first time when lane N+1 is reachable.

This problem has a precise solution.
1. We get rid of speeds by switching to time. For each lane we calculate the time intervals, when there is no car in this lane.
2. Having the time intervals we do simple search:
a) for the first lane, a frog can appear at the lane at any moment when there are no cars (i.e., all intervals);
b) knowing which intervals are accessible at lane i-1, we can easily calculate when a frog can appear at lane i: we simply intersect the accessible intervals at lane i-1 and "no car" intervals at lane i;
c) finally, if there is at least one interval accessible to a frog at lane n (the last lane), then the road can be crossed and vice versa;

The complexity of the solution is linear to the number of cars.

There is no right answer for this and its a thought provoking question.

There are many variables and many assumptions to be made.
Assumptions:
1. Each car is of length 1 and Speed 1.
2. Assumed the Lane is finite (like 10 meters, so 10 slots and only up to 10 cars at a time)
3. The Frog will jump in to the first empty spot in Lane 1.
4. The Jump/Wait will take time-1.
5. The frog can jump both backwards or forwards.

Algorithm:

1. Jump in to the first empty spot(say slot-3) in Lane 1
2. See if the previous spot in the next lane is empty( slot-2 in Lane-2), then Jump
     Else if (see if there is a vehicle behind frog in the current lane) then Jump back
     Else wait
3. Keep adding the Lanes in the Queue as we progress and Do BFS.
4. If the Current Lane is destination, then get out of the loop