single-lane bridge problem

If you're unfamiliar with the problem, it's something like this.

I didn't come to ask for an answer, I have actually finished all of my coding. I have just found that my solution doesn't solve it the best way possible, because my solution only allows one car at a time on the bridge. I was hoping I could get some tips about how to go about using sem_wait and sem_post to solving this problem. I hope to allow traffic flowing the same direction to flow together and not one at a time.

My solution currently looks something like:

(default sem_t north and south = 1 for unlocked for 1 car)

IF northcar then sem_wait(south), sem_wait(north). Cross the bridge, and then sem_post(north), sem_post(south). This is obviously wrong开发者_运维知识库 because it's locking the bridge from all cars other than the one on it. I want to enable traffic to flow together. Any ideas?

I am using randomly generated traffic which adds a bit of complexity to it.

In real life you would solve this problem with a traffic light which is either red-north/green-south, green-north/red-south, or red-north/red-south, and sensors in the approach and exit lanes at both ends of the bridge.

Suppose the light starts out red-north/green-south. Cars can flow from south to north without stopping. When a car approaches from the north, it stops at the red light and triggers the north approach sensor. That makes the light go red-south, but it's still red-north as well. When all the cars currently on the bridge have left (triggering the north exit sensor on their way out) the light can change to green-north. That state persists until another car comes from the south and triggers the south approach sensor.

Think about how you'd translate that into code. (You'll need to use the counting property of semaphores.)

Single Lane Highway Problem Description Certain number of cars are passing a single lane road. Speeds of all cars vary. It is easy to see, that depending on the speeds of the cars various groups will be formed.

Being a single lane road passing/overtaking is not allowed. Given speeds of cars, calculate how many groups can be formed if all possible permutations are taken into account. Refer to example1 for better understanding.

Print number of groups divided by the number of permutations.

Constraints

0 <= N < 10 ^ 5

0 <= speed of individual vehicle < 10 ^ 9

Input First line contains an integer N, which denotes the number of vehicles

Second line contains N space separated integers which denotes the speed of the individual vehicle.

Output Print number of groups divided by the number of permutations rounded upto 6 decimal places.

Time Limit 1

Example 1

Input 3

10 20 30

Output

1.833333

Explanation:

So all possible permutations are:

{10 20 30} {10 30 20}

{20} {10 30}
{20 30} {10}
{30} {10 20}
{30 20} {10}

So here there are total 6 permutations, and total number of groups are 11.

So, output is 11/6 = 1.833333

Example 2

Input 4

56 78 13 92

Output

2.083333

Explanation:

So here there are total of 24 permutations,

For example:

{56 78 13 92}
{92} {13 78 56}
{56} {13 92 78}
{78 92} {13 56}
.
.

So on and so forth. The total number of groups are 50.

So, the output is 50/24 = 2.083333

This is some pseudo python I just whipped up. Basically block one way and let a limited number cars through. Depending on how you're using your variables, this might be totally wrong:

function main():
    while(true):
        if(north_car):
            let_north_cars_through()
        if(south_car):
            let_south_cars_through()


function let_south_cars_through():
    sem_wait(north)
    for(i = 0; i < max cars; i++):
        if(south_car):
            cross_bridge()
        else:
            break;

    sem_post(north)

function let_north_cars_through()
    sem_wait(south)
    for(i = 0; i < max cars; i++):
        if(north_car):
            cross_bridge()
        else:
            break;

    sem_post(south)