title: cutting cost algorithm optimization
body: <p>I have a wood sheet and have given N mark on wood sheet.Now i have to cut all the marks on wood sheet such that cost of cutting all the marks in minimum.Now suppose i first cut the i th mark then the cost is given by using two multipliers a and b which are inputs and the cost is a*(left)+b*(right) where left and right are the size of remaining part of the wood after cutting .for example if i have a wood of length 10 and a=3 and b=4 and if i have mark list for ex: [1,3,5,7,10] so i cant cut first and last mark because they are the starting and end point of the wood so suppose if i start with mark 7 first then cost of cutting will be 3*(7-1)+4*(10-7)=18+12=30 and now the wood which i would have is one starting with mark 1 to mark 7 and other would be one with mark 7 to the end of the wood ad i would repeat the process till all of the marks have been cut .</p>
  
  <p>Now after reading the question it immediately came to my mind that in order to cut the wood in minimum cost i first need to find the mid point(median of cut points) and there i should cut the wood and repeat this process again and again till the wood has no cut points left but i am having problem in solving the right wood obtained after cutting  </p>
  
  <p>sample input:wood having cut with [1,3,5,9,16,22] would have minimum cost=163 when we first start with median 9 then we would have wood of mark[1,3,5,9] and [9,16,22] now first solving the left wood we would have [1,3,5][5,9],now again cutting we have [1,3][3,5][5,9] and the one which was left [9,16,22] now on operating this wood we have cut all the marks and the list would be [1,3][3,5][5,9][9,16][16,22] and the cost on this operation would be minimum</p>
  
  <p>here is my code:</p>
  
  <pre><code>for _ in range(int(input())):     #no of test cases 
  a,b=map(int,input().split())      #multiplier element of cost ex: 3,4
  n=int(input())                    #total number of cuts ex: 6
  x=list(map(int,input().split()))  #where the cuts are the wood ex:
                                    #[1,3,5,9,16,22]
  
  lis=[]
  cost=0
  
  average=sum(x)/len(x)
  median=min(x,key=lambda X:abs(X-average))  #calculated the median 
  
  cost+=a*(median-x[0])+b*(x[-1]-median)  #calculated the cost of cutting 
  print(cost)
  var=x.index(median)                      #found the index of median
  x_left=x[:var+1]                         #split the wood in left and right
  x_right=x[var:]
  lis.append(x_right)
  while(len(x_left)&gt;2):       #done the same process going first on left wood    
  
      average=sum(x_left)/len(x_left)
      median=min(x_left,key=lambda X:abs(X-average))
      cost+=a*(median-x_left[0])+b*(x_left[-1]-median)
      var=x.index(median)
      x_left=x_left[:var+1]
      x_right=x_left[var:] #this wood would again have right component so 
                           #stored that right side in list named lis
      lis.append(x_right)
  print(cost)             #fully solved by moving leftwards
  print(lis)
  tt=len(lis)
  for i in lis:           #but the problem start here i have all the right 
                          #pieces of wood that i had stored in lis but now i 
                          #can't evaluate them
      if(len(i)&lt;3):
          lis.pop(lis.index(i))
  
  
      else:
          continue
  print(lis)
  while(tt!=0):
      xx=lis.pop(0)
      ttt=len(xx)
      if(ttt&gt;2):
          average=sum(xx)/ttt
          median=min(xx,key=lambda X:abs(X-average))
          cost+=a*(median-xx[0])+b*(xx[-1]-median)
          var=x.index(median)
          x_left=xx[:var+1]
          x_right=xx[var:]
          if(len(x_left)&gt;2):
              lis.append(x_left)
          if(len(x_right)&gt;2):
              lis.append(x_right)
  print(cost)
  </code></pre>