Centerpiece Code

A centerpiece for a wedding is to set with terracotta pots of the same size. A group of pots placed one over the other is called a stack. There are 'N’ such stacks, the stacks being arranged in order. The number of pots in a stack is called the 'height' of the stack and this number is represented by array elements (a[]). Water is continuously poured into the first stack. Water from the first stack flows through the other stacks and reaches the last stack as follows:

Water can flow from any stack to its next stack if the height of the former stack is more than or equal to the height of the next stack; for instance, if the height of the first stack is 4 and that of the second stack is 3, water can flow from the first stack to the second. If the height of any stack is less than that of its next stack, remove some pots from the next stack to make its height equal to or less than its preceding stack.

So, to keep the water flowing from the first stack to the last, some pots are to be removed from some stacks.

The task here is to find the minimum number of pots that are to be removed to maintain this waterflow.

Example 1:

Input

5 -> Value of N

{6,2,5,1,3} -> a[], Elements a[0] to a[N-1], where each input element is separated by a new line

Output: 5

Explanation:

From the inputs given above: Number of stack of pots: 5 Stack 1: 6 pots

Stack 2: 2 pots

Stack 3: 5 pots

Stack 4: 1 pots

Stack 5: 3 pots

 

If the water is poured in stack 1

Step 1:Watter flows to stack 2, as height of stack 2 is less than the height of stack1(2< 6).

Current height of stacks = {6,2,5,1,3}

Step 2: Water does not flow from stack 2 to stack 3,as the height of stack 3 more than the height of stack 2 (5 > 2). So, remove 3 pots from stack 3 to make its height equal to that of stack 2.

Current height of stacks = {6,2,2,1,3}

Step 3: Water flows to stack 4, as the height of stack 4 is less then the height of stack 3 (1<2).

Current height of stacks = {6,2,2,1,3}

Step:4: Water does not flow to stack 5, as the height Of stack 5 is more than the height of stack 4 (3 > 1).

So, remove 2 pots from stack 5 to make its height equal to that of stack 4.

In total, 5 pots have to be removed (3 from stack 3 and 2 from stack 5). After removing the pots, the heights of the stacks will be {6,2,2,1,1}, which will allow the water from the first pot of the first stack to flow till the first pot of the last stack

Hence the output is 5.

 

Example 2:

3-value of N

{1,2,3}-a[]

Output:

3

Step 1: current stack is {1,1,3}

Step 2: 2 pots from stack 3 to make its height equal to of stack2

Current height of stack:{1,1,3}

 

Hence the output is 3.

 

Code: Python Solution

 

 

N=int(input())

A=[]

for i in range(N):

    A.append(int(input()))

count=0

op=[]

for i in range(N):

    if(i<N-1):

        if(A[i]>A[i+1]):

            pass

        elif(A[i]<A[i+1]):

            count=count+(A[i+1]-A[i])

            A[i+1]=A[i+1]-(A[i+1]-A[i])

print(count)