4.5 Dhrumil's: Google Interview

Score: 25pts

Time Limit: 0.32 sec

You are on the 1st floor of the building waiting for your interview at google. But there’s a catch, you dont know on which floor your interview is.

The building has n floors, you have to print n numbers, which is the minimum cost required to reach each of the floors from 1 to n

If you are taking the stairs from floor x to floor y, the cost taken is =∑ a[i] where i is from x -> y

If you are taking the lift from floor x to floor y, the cost taken is = c+( ∑ b[i] where i is from x -> y )

You are given arrays a and b of n - 1 size out of which the ith number denotes the cost from ith to i + 1th floor

The building has n floors, you have to print n numbers, which is the minimum cost required to reach each of the floors from 1 to n

If you are taking the stairs from floor x to floor y, the cost taken is =∑ a[i] where i is from x -> y

If you are taking the lift from floor x to floor y, the cost taken is = c+( ∑ b[i] where i is from x -> y )

You are given arrays a and b of n - 1 size out of which the ith number denotes the cost from ith to i + 1th floor

Constraints

size of a[i] can range from 1 to 10^3

Input Format

First line contains two space seperated integers n and c.

Next line contains input for array a of size n-1.

Last line contains input for array b of size n-1.

Next line contains input for array a of size n-1.

Last line contains input for array b of size n-1.

Output Format

The output format will be a single line containing the minimum cost required to reach each floor from 1 to n, separated by spaces. For the given example, the output format is:

Example 1

Input:

n = 10, c = 2

a = [7, 6, 18, 6, 16, 18, 1, 17, 17]

b = [6 ,9, 3, 10, 9, 1, 10, 1, 5]

Output:

0 7 13 18 24 35 36 37 40 45

Explanation:

Best ans for floor 1 = 0 (You are already on floor 1)

Best ans for floor 2 = 7 (Take stairs)

Best ans for floor 3 = 13 (Take stairs)

Best ans for floor 4 = 18 (Take lift from floor 3 to floor 4)

Best ans for floor 5 = 24 (Stairs again)

Best ans for floor 6 = 35 (Take lift from floor 5 to floor 6)

Best ans for floor 7 = 36 (jo lift 5th floor se li thi, wahi se 7th pe utro)

Best ans for floor 8 = 37 (stairs 🙂)

Best ans for floor 9 = 40 (8th floor se 9th floor tak lift)

Best ans for floor 10 = 45 (Wahi lift mai 10th floor tak aajao)

If you take a new lift, then only cost c adds up, you can travel multiple floors in same lift, then c will only be added once

n = 10, c = 2

a = [7, 6, 18, 6, 16, 18, 1, 17, 17]

b = [6 ,9, 3, 10, 9, 1, 10, 1, 5]

Output:

0 7 13 18 24 35 36 37 40 45

Explanation:

Best ans for floor 1 = 0 (You are already on floor 1)

Best ans for floor 2 = 7 (Take stairs)

Best ans for floor 3 = 13 (Take stairs)

Best ans for floor 4 = 18 (Take lift from floor 3 to floor 4)

Best ans for floor 5 = 24 (Stairs again)

Best ans for floor 6 = 35 (Take lift from floor 5 to floor 6)

Best ans for floor 7 = 36 (jo lift 5th floor se li thi, wahi se 7th pe utro)

Best ans for floor 8 = 37 (stairs 🙂)

Best ans for floor 9 = 40 (8th floor se 9th floor tak lift)

Best ans for floor 10 = 45 (Wahi lift mai 10th floor tak aajao)

If you take a new lift, then only cost c adds up, you can travel multiple floors in same lift, then c will only be added once