Luogu P1007 - Single-plank Bridge

Computer Science Level pending

The war has entered a critical time. You are the leader of the transport team, leading the transport force to deliver supplies to the front. The transportation task is as boring as a problem. You want to find some excitement, so you order your soldiers to admire the scenery on a log bridge in front, and you stay under the bridge to admire the soldiers. The soldiers were very angry because the single-plank bridge was very narrow and could only accommodate one person. If there are two people walking towards each other on the bridge to meet, then the two of them will not be able to bypass each other, and only one person can turn back and get off the bridge and let the other person pass first. However, multiple people can stay in the same location at the same time.

Suddenly, you received a message from the command center that enemy bombers are flying towards the single-plank bridge where you are! To be safe, your troops must withdraw the log bridge. The length of the single-plank bridge is LL, and soldiers can only stay where the coordinates are integers. The speed of all soldiers is 11, but a soldier arrives at a position with coordinates 00 or L+1L+1 at a certain moment, and he leaves the single-plank bridge.

Each soldier has an initial facing direction, they will walk in this direction at a constant speed, and will not change direction by themselves. However, if two soldiers meet face to face, they cannot pass each other, so they turn around and continue walking. It doesn't take any time to turn around.

Because of the previous anger, you can no longer control your soldiers. Even, you don't even know the direction each soldier is facing initially. Therefore, you want to know how long it takes at least for your troops to evacuate the log bridge. In addition, the headquarters is also arranging to stop the enemy's attack, so you also need to know how long it takes at most for your troops to evacuate the log bridge.

How to submit:

The pastebin below has 1010 inputs. Each input has the format:

  • Line 1: An integer LL, the length of the log bridge, where the coordinates are 1,2,,L1,2,\cdots,L.

  • Line 2: An integer NN, the number of soldiers.

  • Line 3: NN integers, the initial coordinates for each soldier.

Output: Two integers L,RL, R. LL is the minimum time it takes for your troops to evacuate the log bridge, RR is the maximum time it takes for your troops to evacuate the log bridge.

Then submit the sum of 2RL2R-L of each output.

Inputs are here

Input restrictions:

  • No two soldiers are on the same coordinate initially.

  • NL5000N \leq L \leq 5000.

Luogu Problem Set


Problem Loading...

Note Loading...

Set Loading...