Irrigation Walk Steps - FAANG Problems | Repovive

FNG1. Irrigation Walk Steps

2s256 MB

This problem is based on a Google interview problem described here.

You have $n$ plants in a row, numbered from $0$ to $n-1$ . Plant $i$ needs $p_i$ units of water. You start at the river (position $-1$ ) with a watering can that holds at most $K$ units of water, initially full.

You walk forward one plant at a time. You have two choices:

If you have enough water in your can, you step forward, water the plant and continue to the next one.
If you do not have enough water(before reaching that plant), you must first walk back to the river, refill your can to full capacity $K$ at the river, and then walk back to that plant to water it.

Each step between adjacent positions (including between the river and plant $0$ ) counts as one step.

Return the total number of steps taken to water all plants.

Constraints

$1 \le n \le 10^5$
$1 \le K \le 10^9$
$1 \le p_i \le K$

Input

\begin{array}{l} n \quad K \\ p_0 \quad p_1 \quad \cdots \quad p_{n-1} \end{array}

Output

$ans$

Samples

Input

4 5
2 2 3 3

Explanation

\begin{array}{l} \text{\textbf{Timeline Map}} \\ \text{River at } [-1], \quad \text{Plants } 0 \rightarrow 3 \\ \hline \\ \begin{array}{lccccc} \textbf{Action State} & \mathbf{[-1] \text{ River}} & \mathbf{[0] \text{ Plnt}} & \mathbf{[1] \text{ Plnt}} & \mathbf{[2] \text{ Plnt}} & \mathbf{[3] \text{ Plnt}} \\ \hline \text{Start Can: } K = 5 & \text{\color{blue}Start} & 2 & 2 & 3 & 3 \\ \\ \text{Step 1 \& 2 (Forward)} & \longleftrightarrow & \color{green}{\mathbf{\textcircled{\checkmark}}} & \color{green}{\mathbf{\textcircled{\checkmark}}} & \text{Can: } 1 & \text{Can: } 1 \\ & & \text{\small{Can: 3}} & \text{\small{Can: 1}} & \text{\small{(Low!)}} & \\ \\ \text{Refill 1 (Trip to 2)} & \xleftarrow{\quad \text{Back: 2 steps} \quad} & \longleftarrow & \longleftarrow & \text{Can: 1} & \text{Can: 1} \\ & \xrightarrow[\quad \text{Forward: 3 steps} \quad]{} & \longrightarrow & \longrightarrow & \color{red}{\mathbf{\textcircled{\checkmark}}} & \text{Can: } 2 \\ & & & & \text{\small{Can: 2}} & \text{\small{(Low!)}} \\ \\ \text{Refill 2 (Trip to 3)} & \xleftarrow{\qquad\qquad \text{Back: 3 steps} \qquad\qquad} & \longleftarrow & \longleftarrow & \longleftarrow & \text{Can: 2} \\ & \xrightarrow[\qquad\qquad \text{Forward: 4 steps} \qquad\qquad]{} & \longrightarrow & \longrightarrow & \longrightarrow & \color{red}{\mathbf{\textcircled{\checkmark}}} \\ & & & & & \text{\small{Can: 2}} \\ \end{array} \\ \\ \hline \text{\textbf{Final Footsteps Sum: }} 2 \text{ (Initial)} + 5 \text{ (Trip 1)} + 7 \text{ (Trip 2)} = \color{cyan}{\mathbf{14 \text{ Total Steps}}} \end{array}

Output

Input

3 3
1 1 1

Explanation

\begin{array}{l} \text{\textbf{Timeline Map}} \\ \text{River at } [-1], \quad \text{Plants } 0 \rightarrow 2 \\ \hline \\ \begin{array}{lcccc} \textbf{Action State} & \mathbf{[-1] \text{ River}} & \mathbf{0 \text{ Plnt}} & \mathbf{1 \text{ Plnt}} & \mathbf{2 \text{ Plnt}} \\ \hline \text{Start Can: } K = 3 & \text{\color{blue}Start} & 1 & 1 & 1 \\ \\ \text{Step 1, 2 \& 3 (Forward)} & \xrightarrow{\quad \text{Walk Forward} \quad} & \color{green}{\mathbf{\textcircled{\checkmark}}} & \color{green}{\mathbf{\textcircled{\checkmark}}} & \color{green}{\mathbf{\textcircled{\checkmark}}} \\ & & \text{\small{Can: 2}} & \text{\small{Can: 1}} & \text{\small{Can: 0}} \\ \end{array} \\ \\ \hline \text{\textbf{Final Footsteps Sum: }} 3 \text{ Steps Forward Only} = \color{cyan}{\mathbf{3 \text{ Total Steps}}} \end{array}

Output

Input

1 5
5

Explanation

\begin{array}{l} \text{\textbf{Timeline Map}} \\ \text{River at } [-1], \quad \text{Plants } 0 \rightarrow 0 \\ \hline \\ \begin{array}{lcc} \textbf{Action State} & \mathbf{[-1] \text{ River}} & \mathbf{0 \text{ Plnt}} \\ \hline \text{Start Can: } K = 5 & \text{\color{blue}Start} & 5 \\ \\ \text{Step 1 (Forward)} & \xrightarrow{\quad \text{1 Step} \quad} & \color{green}{\mathbf{\textcircled{\checkmark}}} \\ & & \text{\small{Can: 0}} \\ \end{array} \\ \\ \hline \text{\textbf{Final Footsteps Sum: }} 1 \text{ Step Forward Only} = \color{cyan}{\mathbf{1 \text{ Total Steps}}} \end{array}

Output

FNG1. Irrigation Walk Steps

2s256 MB

This problem is based on a Google interview problem described here.

You walk forward one plant at a time. You have two choices:

If you have enough water in your can, you step forward, water the plant and continue to the next one.
If you do not have enough water(before reaching that plant), you must first walk back to the river, refill your can to full capacity $K$ at the river, and then walk back to that plant to water it.

Each step between adjacent positions (including between the river and plant $0$ ) counts as one step.

Return the total number of steps taken to water all plants.

Constraints

$1 \le n \le 10^5$
$1 \le K \le 10^9$
$1 \le p_i \le K$

Input

\begin{array}{l} n \quad K \\ p_0 \quad p_1 \quad \cdots \quad p_{n-1} \end{array}

Output

$ans$

Samples

Input

4 5
2 2 3 3

Explanation

\begin{array}{l} \text{\textbf{Timeline Map}} \\ \text{River at } [-1], \quad \text{Plants } 0 \rightarrow 3 \\ \hline \\ \begin{array}{lccccc} \textbf{Action State} & \mathbf{[-1] \text{ River}} & \mathbf{[0] \text{ Plnt}} & \mathbf{[1] \text{ Plnt}} & \mathbf{[2] \text{ Plnt}} & \mathbf{[3] \text{ Plnt}} \\ \hline \text{Start Can: } K = 5 & \text{\color{blue}Start} & 2 & 2 & 3 & 3 \\ \\ \text{Step 1 \& 2 (Forward)} & \longleftrightarrow & \color{green}{\mathbf{\textcircled{\checkmark}}} & \color{green}{\mathbf{\textcircled{\checkmark}}} & \text{Can: } 1 & \text{Can: } 1 \\ & & \text{\small{Can: 3}} & \text{\small{Can: 1}} & \text{\small{(Low!)}} & \\ \\ \text{Refill 1 (Trip to 2)} & \xleftarrow{\quad \text{Back: 2 steps} \quad} & \longleftarrow & \longleftarrow & \text{Can: 1} & \text{Can: 1} \\ & \xrightarrow[\quad \text{Forward: 3 steps} \quad]{} & \longrightarrow & \longrightarrow & \color{red}{\mathbf{\textcircled{\checkmark}}} & \text{Can: } 2 \\ & & & & \text{\small{Can: 2}} & \text{\small{(Low!)}} \\ \\ \text{Refill 2 (Trip to 3)} & \xleftarrow{\qquad\qquad \text{Back: 3 steps} \qquad\qquad} & \longleftarrow & \longleftarrow & \longleftarrow & \text{Can: 2} \\ & \xrightarrow[\qquad\qquad \text{Forward: 4 steps} \qquad\qquad]{} & \longrightarrow & \longrightarrow & \longrightarrow & \color{red}{\mathbf{\textcircled{\checkmark}}} \\ & & & & & \text{\small{Can: 2}} \\ \end{array} \\ \\ \hline \text{\textbf{Final Footsteps Sum: }} 2 \text{ (Initial)} + 5 \text{ (Trip 1)} + 7 \text{ (Trip 2)} = \color{cyan}{\mathbf{14 \text{ Total Steps}}} \end{array}

Output

Input

3 3
1 1 1

Explanation

\begin{array}{l} \text{\textbf{Timeline Map}} \\ \text{River at } [-1], \quad \text{Plants } 0 \rightarrow 2 \\ \hline \\ \begin{array}{lcccc} \textbf{Action State} & \mathbf{[-1] \text{ River}} & \mathbf{0 \text{ Plnt}} & \mathbf{1 \text{ Plnt}} & \mathbf{2 \text{ Plnt}} \\ \hline \text{Start Can: } K = 3 & \text{\color{blue}Start} & 1 & 1 & 1 \\ \\ \text{Step 1, 2 \& 3 (Forward)} & \xrightarrow{\quad \text{Walk Forward} \quad} & \color{green}{\mathbf{\textcircled{\checkmark}}} & \color{green}{\mathbf{\textcircled{\checkmark}}} & \color{green}{\mathbf{\textcircled{\checkmark}}} \\ & & \text{\small{Can: 2}} & \text{\small{Can: 1}} & \text{\small{Can: 0}} \\ \end{array} \\ \\ \hline \text{\textbf{Final Footsteps Sum: }} 3 \text{ Steps Forward Only} = \color{cyan}{\mathbf{3 \text{ Total Steps}}} \end{array}

Output

Input

1 5
5

Explanation

\begin{array}{l} \text{\textbf{Timeline Map}} \\ \text{River at } [-1], \quad \text{Plants } 0 \rightarrow 0 \\ \hline \\ \begin{array}{lcc} \textbf{Action State} & \mathbf{[-1] \text{ River}} & \mathbf{0 \text{ Plnt}} \\ \hline \text{Start Can: } K = 5 & \text{\color{blue}Start} & 5 \\ \\ \text{Step 1 (Forward)} & \xrightarrow{\quad \text{1 Step} \quad} & \color{green}{\mathbf{\textcircled{\checkmark}}} \\ & & \text{\small{Can: 0}} \\ \end{array} \\ \\ \hline \text{\textbf{Final Footsteps Sum: }} 1 \text{ Step Forward Only} = \color{cyan}{\mathbf{1 \text{ Total Steps}}} \end{array}

Output