[Solution] Two Trains solution codechef

Two Trains solution codechef – There are 2 trains A and B and N stations in a line from 1 to N in order. There is also an array P of length N-1 such that P_i (1\le i \lt N) denotes the amount of time any train takes to go from the i-th station to the (i+1)-th station.

Table of Contents

[Solution] Two Trains solution codechef

Initially, both trains are at station 1. Train A departs from station 1 and stops directly at station N. For safety purposes, it is maintained that train B cannot depart from station i unless train A has already reached station (i+1) (1 \le i \lt N).

Find the minimum time after which train B reaches station N, once train A departs from station 1.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains an integer N, denoting number of stations.
    • The next line contains N-1 space-separated integers, P_1,P_2,\ldots ,P_{N-1}.

Output Format

For each test case, output on a new line the minimum time after which train B reaches station N.

[Solution] Two Trains solution codechef

  • 1 \leq T \leq 100
  • 2 \leq N \leq 10^5
  • 1 \leq P_i \leq 10^3
  • The sum of N over all test cases won’t exceed 10^5.

Sample 1:

Input

Output

3
2
4
3
3 5
4
5 2 6
8
13
19

Two Trains solution codechef Explanation:

Test case 1: A reaches station 2 at t=4 and at this time B departs from station 1 and reaches station 2 at t=4+4=8.

Test case 1: Following is the timeline of two trains-

  • At t=3A reaches station 2 and B departs from station 1.
  • At t=6B reaches station 2 but A has not yet reached station 3, so train B will wait at station 2.
  • At t=8A reaches station 3 and B departs from station 2.
  • At t=8+5=13, train B reaches station 3.

For Solution

“Click Here”

Leave a Comment