Go Go Home
There are NN apartments along a number line, numbered 11 through NN. Apartment ii is located at coordinate XiXi. Also, the office of Prepbyte Inc. is located at coordinate SS. Every employee of Prepbytes lives in one of the NN apartments. There are PiPi employees who are living in Apartment ii.
All employees of Prepbytes are now leaving the office altogether. Since they are tired from work, they would like to get home by the company’s bus. Prepbytes owns only one bus, but it can accommodate all the employees. This bus will leave coordinate SS with all the employees and move according to the following rule:
Everyone on the bus casts a vote on which direction the bus should proceed, positive or negative. (The bus is autonomous and has no driver.) Each person has one vote, and abstaining from voting is not allowed. Then, the bus moves a distance of 1 in the direction with the greater number of votes. If a tie occurs, the bus moves in a negative direction. If there is an apartment at the coordinate of the bus after the move, all the employees who live there get off.
Repeat the operation above as long as there are one or more employees on the bus.
For a specific example, see Sample Input 11.
The bus takes one second to travel a distance of 1. The time required to vote and get off the bus is ignorable.
Every employee will vote so that he himself/she herself can get off the bus at the earliest possible time. Strictly speaking, when a vote is taking place, each employee sees which direction results in the earlier arrival at his/her apartment, assuming that all the employees follow the same strategy in the future. Based on this information, each employee makes the optimal choice, but if either direction results in the arrival at the same time, he/she casts a vote in the negative direction.
Find the time the bus will take from departure to arrival at the last employees’ apartment. It can be proved that, given the positions of the apartments, the numbers of employees living in each apartment, and the initial position of the bus, the future movement of the bus is uniquely determined, and the process will end in a finite time.
The first line of input contains two integers NN and SS – denoting the number of apartments and the S-coordinate of Prepbytes office. Following N lines of the input file contains 2 integers per row XiXi and PiPi.
Print the number of seconds the bus will take from departure to arrival at the last employees’ apartment.
1≤N≤1051≤N≤105 1≤S≤1091≤S≤109 1≤X1<X2<…<XN=1091≤X1<X2<…<XN=109 1≤Pi≤109(1≤i≤N)1≤Pi≤109(1≤i≤N) All values in input are integers.
3 2 1 3 3 4 4 2
Note: Assume that the bus moves in the negative direction first. Then, the coordinate of the bus changes from 2 to 1, and the employees living in Apartment 1 get off. The movement of the bus after that is obvious: it just continues moving in a positive direction. Thus, if the bus moves in the negative direction first, the coordinate of the bus changes as 2,1,2,3,42,1,2,3,4 from departure. The time it takes to get home for the employees living in Apartment 1,2,31,2,3 are 1,3,41,3,4 seconds, respectively.
Next, assume that the bus moves in a positive direction first. Then, the coordinate of the bus changes from 22 to 33, and the employees living in Apartment 22 get off. Afterward, the bus starts heading to Apartment 1, because there are more employees living in Apartment 1 than in Apartment 33. Then, after arriving at Apartment 1, the bus heads to Apartment 33. Thus, if the bus moves in the positive direction first, the coordinate of the bus changes as 2,3,2,1,2,3,42,3,2,1,2,3,4 from departure. The time it takes to get home for the employees living in Apartment 1,2,31,2,3 are 3,1,63,1,6 seconds, respectively.
Therefore, in the beginning, the employees living in Apartment 11 or 33 will try to move the bus in a negative direction. On the other hand, the employees living in Apartment 22 will try to move the bus in a positive direction in the beginning. There are a total of 3+2=53+2=5 employees living in Apartment 11 and 33 combined, which is more than those living in Apartment 22, which is 44. Thus, the bus will move in the negative direction first, and the coordinate of the bus will change as 2,1,2,3,42,1,2,3,4 from departure.
Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.
JULY 2021 CODING MARATHON
- Shortest String Solution
- Least Common Multiple Solution
- String Transformation Solution
- Dark Moments Solution
- Go Go Home Solution
- Construct Rectangle Solution
- Arrange Guest Solution
- New Array Subarray Solution