[Solution] Late For Work solution codeforces

Late For Work solution codeforces – Debajyoti has a very important meeting to attend and he is already very late. Harsh, his driver, needs to take Debajyoti to the destination for the meeting as fast as possible.

Table of Contents

[Solution] Late For Work solution codeforces

Harsh needs to pick up Debajyoti from his home and take him to the destination so that Debajyoti can attend the meeting in time. A straight road with 𝑛n traffic lights connects the home and the destination for the interview. The traffic lights are numbered in order from 11 to 𝑛n.

Each traffic light cycles after 𝑡t seconds. The 𝑖i-th traffic light is greengreen (in which case Harsh can cross the traffic light) for the first 𝑔𝑖gi seconds, and redred (in which case Harsh must wait for the light to turn greengreen) for the remaining (𝑡𝑔𝑖)(t−gi) seconds, after which the pattern repeats. Each light’s cycle repeats indefinitely and initially, the 𝑖i-th light is 𝑐𝑖ci seconds into its cycle (a light with 𝑐𝑖=0ci=0 has just turned greengreen). In the case that Harsh arrives at a light at the same time it changes colour, he will obey the new colour. Formally, the 𝑖i-th traffic light is greengreen from [0,𝑔𝑖)[0,gi) and redred from [𝑔𝑖,𝑡)[gi,t) (after which it repeats the cycle). The 𝑖i-th traffic light is initially at the 𝑐𝑖ci-th second of its cycle.

From the 𝑖i-th traffic light, exactly 𝑑𝑖di seconds are required to travel to the next traffic light (that is to the (𝑖+1)(i+1)-th light). Debajyoti’s home is located just before the first light and Debajyoti drops for the interview as soon as he passes the 𝑛n-th light. In other words, no time is required to reach the first light from Debajyoti’s home or to reach the interview centre from the 𝑛n-th light.

Harsh does not know how much longer it will take for Debajyoti to get ready. While waiting, he wonders what is the minimum possible amount of time he will spend driving provided he starts the moment Debajyoti arrives, which can be anywhere between 00 to  seconds from now. Can you tell Harsh the minimum possible amount of time he needs to spend on the road?

[Solution] Late For Work solution codeforces

The first line of input will contain two integers, 𝑛n and 𝑡t (2𝑛21052≤n≤2⋅1052𝑡1092≤t≤109) denoting the number of traffic lights and the cycle length of the traffic lights respectively.

𝑛n lines of input follow. The 𝑖i-th line will contain two integers 𝑔𝑖gi and 𝑐𝑖ci (1𝑔𝑖<𝑡1≤gi<t0𝑐𝑖<𝑡0≤ci<t) describing the 𝑖i-th traffic light.

The following line of input contains 𝑛1n−1 integers 𝑑1,𝑑2,,𝑑𝑛1d1,d2,…,dn−1 (0𝑑𝑖1090≤di≤109) — the time taken to travel from the 𝑖i-th to the (𝑖+1)(i+1)-th traffic light.

Output

Output a single integer — the minimum possible amount of time Harsh will spend driving.

Examples
input

Copy
5 10
4 2
7 3
3 6
5 2
8 0
1 2 3 4

[Solution] Late For Work solution codeforces

Copy
11
input

Copy
6 9
5 3
5 5
7 0
5 8
7 7
6 6
0 0 0 0 0
output

Copy
3

[Solution] Late For Work solution codeforces

In the first example, Harsh can do the following:

  • Initially, the 55 traffic lights are at the following seconds in their cycle: {2,3,6,2,0}{2,3,6,2,0}.
  • An optimal time for Harsh to start is if Debajyoti arrives after 11 second. Note that this 11 second will not be counted in the final answer.
  • The lights will be now at {3,4,7,3,1}{3,4,7,3,1}, so Harsh can drive from the 11-st light to the 22-nd light, which requires 11 second to travel.
  • The lights are now at {4,5,8,4,2}{4,5,8,4,2}, so Harsh can continue driving, without stopping, to the 33-rd light, which requires 22 seconds to travel.
  • The lights are now at {6,7,0,6,4}{6,7,0,6,4}, so Harsh continues to the 44-th light, which requires 33 seconds to travel.
  • The lights are now at {9,0,3,9,7}{9,0,3,9,7}. Harsh must wait 11 second for the 44-th light to turn green before going to the 55-th light, which requires 44 seconds to travel.
  • The lights are now at {4,5,8,4,2}{4,5,8,4,2}, so Harsh can continue traveling, without stopping, to the meeting destination. The total time that Harsh had to drive for is 1+2+3+1+4=111+2+3+1+4=11 seconds.

In the second example, Harsh can do the following:

  • Initially, the 66 traffic lights are at the following seconds in their cycle: {3,5,0,8,7,6}{3,5,0,8,7,6}.
  • An optimal time for Harsh to start is if Debajyoti arrives after 11 second. Note that this 11 second will not be counted in the final answer.
  • The lights will be now at {4,6,1,0,8,7}{4,6,1,0,8,7}, so Harsh can drive from the 11-st light to the 22-nd light, which requires 00 seconds to travel.
  • The lights are still at {4,6,1,0,8,7}{4,6,1,0,8,7}. Harsh must wait 33 seconds for the 22-nd light to turn green, before going to the 33-rd light, which requires 00 seconds to travel.
  • The lights are now at {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh continues to the 44-th light, which requires 00 seconds to travel.
  • The lights are still at {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh continues to the 55-th light, which requires 00 seconds to travel.
  • The lights are still at {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh continues to the 66-th light, which requires 00 seconds to travel.
  • The lights are still at {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh can continue traveling, without stopping, to the meeting destination. The total time that Harsh had to drive for is 0+3+0+0+0=30+3+0+0+0=3 seconds.

 

For Solution

“Click Here”

Leave a Comment