


"""simple docstring"""







def 					a__			(				SCREAMING_SNAKE_CASE    :    int				,      SCREAMING_SNAKE_CASE    :    list				):


  '''simple docstring'''







  _enforce_args(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
  if n == 0:
    return 0
  lowerCAmelCase     :     List[str]								=							float("-inf"				)
  for i in range(1				,      n + 1				):
    lowerCAmelCase     :     str								=							max(
        SCREAMING_SNAKE_CASE				,      prices[i - 1] + naive_cut_rod_recursive(n - i				,      SCREAMING_SNAKE_CASE				)				)

  return max_revue
def 					a__			(				SCREAMING_SNAKE_CASE    :    int				,      SCREAMING_SNAKE_CASE    :    list				):


  '''simple docstring'''







  _enforce_args(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
  lowerCAmelCase     :     str								=							[float("-inf"				) for _ in range(n + 1				)]
  return _top_down_cut_rod_recursive(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
def 					a__			(				SCREAMING_SNAKE_CASE    :    int				,      SCREAMING_SNAKE_CASE    :    list				,      SCREAMING_SNAKE_CASE    :    list				):


  '''simple docstring'''







  if max_rev[n] >= 0:
    return max_rev[n]
  elif n == 0:
    return 0
  else:
    lowerCAmelCase     :     Optional[int]								=							float("-inf"				)
    for i in range(1				,      n + 1				):
      lowerCAmelCase     :     List[Any]								=							max(
          SCREAMING_SNAKE_CASE				,      prices[i - 1] + _top_down_cut_rod_recursive(n - i				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)				,      )

    lowerCAmelCase     :     Dict								=							max_revenue

  return max_rev[n]
def 					a__			(				SCREAMING_SNAKE_CASE    :    int				,      SCREAMING_SNAKE_CASE    :    list				):


  '''simple docstring'''







  _enforce_args(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)

  # length(max_rev) = n + 1, to accommodate for the revenue obtainable from a rod of
  # length 0.
  lowerCAmelCase     :     Optional[int]								=							[float("-inf"				) for _ in range(n + 1				)]
  lowerCAmelCase     :     Union[str, Any]								=							0

  for i in range(1				,      n + 1				):
    lowerCAmelCase     :     int								=							max_rev[i]
    for j in range(1				,      i + 1				):
      lowerCAmelCase     :     Optional[int]								=							max(SCREAMING_SNAKE_CASE				,      prices[j - 1] + max_rev[i - j]				)

    lowerCAmelCase     :     Optional[int]								=							max_revenue_i

  return max_rev[n]
def 					a__			(				SCREAMING_SNAKE_CASE    :    int				,      SCREAMING_SNAKE_CASE    :    list				):


  '''simple docstring'''







  if n < 0:
    lowerCAmelCase     :     List[Any]								=							f"""n must be greater than or equal to 0. Got n = {n}"""
    raise ValueError(SCREAMING_SNAKE_CASE				)

  if n > len(SCREAMING_SNAKE_CASE				):
    lowerCAmelCase     :     Dict								=							(
        "Each integral piece of rod must have a corresponding price. "
        f"""Got n = {n} but length of prices = {len(SCREAMING_SNAKE_CASE				)}"""
    )
    raise ValueError(SCREAMING_SNAKE_CASE				)
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     List[Any]								=							[6, 1_0, 1_2, 1_5, 2_0, 2_3]
  lowerCAmelCase     :     List[Any]								=							len(SCREAMING_SNAKE_CASE				)

  # the best revenue comes from cutting the rod into 6 pieces, each
  # of length 1 resulting in a revenue of 6 * 6 = 36.
  lowerCAmelCase     :     Union[str, Any]								=							3_6

  lowerCAmelCase     :     Tuple								=							top_down_cut_rod(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
  lowerCAmelCase     :     Tuple								=							bottom_up_cut_rod(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
  lowerCAmelCase     :     List[Any]								=							naive_cut_rod_recursive(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)

  assert expected_max_revenue == max_rev_top_down
  assert max_rev_top_down == max_rev_bottom_up
  assert max_rev_bottom_up == max_rev_naive


if __name__ == "__main__":
     main()









class 			_lowercase :


       """simple docstring"""




       def __init__(   self							:			Any					,      __lowerCamelCase							:			int       ):


             '''simple docstring'''



             lowerCamelCase__		:				List[str]    =  n
             lowerCamelCase__		:				Union[str, Any]    =  [None] * self.n
             lowerCamelCase__		:				List[str]    =  0  # index of the first element
             lowerCamelCase__		:				Any    =  0
             lowerCamelCase__		:				Any    =  0





       def __len__(   self							:			Tuple       ):


             '''simple docstring'''



             return self.size





       def 						lowerCAmelCase     (   self							:			Optional[int]       ):


             '''simple docstring'''



             return self.size == 0





       def 						lowerCAmelCase     (   self							:			Union[str, Any]       ):


             '''simple docstring'''



             return False if self.is_empty() else self.array[self.front]





       def 						lowerCAmelCase     (   self							:			str					,      __lowerCamelCase							:			List[str]       ):


             '''simple docstring'''



             if self.size >= self.n:
                   raise Exception("QUEUE IS FULL"       )

             lowerCamelCase__		:				Optional[Any]    =  data
             lowerCamelCase__		:				Tuple    =  (self.rear + 1) % self.n
             self.size += 1
             return self





       def 						lowerCAmelCase     (   self							:			Tuple       ):


             '''simple docstring'''



             if self.size == 0:
                   raise Exception("UNDERFLOW"       )

             lowerCamelCase__		:				Any    =  self.array[self.front]
             lowerCamelCase__		:				List[Any]    =  None
             lowerCamelCase__		:				str    =  (self.front + 1) % self.n
             self.size -= 1
             return temp


