4.5 Dhrumil's: Google Interview
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
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.
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
Log In to solve the Question