




'''simple docstring'''





def 			_a   (		SCREAMING_SNAKE_CASE_							:       int   ,   SCREAMING_SNAKE_CASE_							:       list  ):
					_enforce_args(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  )
					if n == 0:
										return 0
					__lowerCAmelCase            = float("-inf"  )
					for i in range(1   ,   n + 1  ):
										__lowerCAmelCase            = 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  ):
					_enforce_args(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  )
					__lowerCAmelCase            = [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  ):
					if max_rev[n] >= 0:
										return max_rev[n]
					elif n == 0:
										return 0
					else:
										__lowerCAmelCase            = float("-inf"  )
										for i in range(1   ,   n + 1  ):
															__lowerCAmelCase            = max(
															    SCREAMING_SNAKE_CASE_   ,   prices[i - 1] + _top_down_cut_rod_recursive(n - i   ,   SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  )   ,   )

										__lowerCAmelCase            = max_revenue

					return max_rev[n]







def 			_a   (		SCREAMING_SNAKE_CASE_							:       int   ,   SCREAMING_SNAKE_CASE_							:       list  ):
					_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            = [float("-inf"  ) for _ in range(n + 1  )]
					__lowerCAmelCase            = 0

					for i in range(1   ,   n + 1  ):
										__lowerCAmelCase            = max_rev[i]
										for j in range(1   ,   i + 1  ):
															__lowerCAmelCase            = max(SCREAMING_SNAKE_CASE_   ,   prices[j - 1] + max_rev[i - j]  )

										__lowerCAmelCase            = max_revenue_i

					return max_rev[n]







def 			_a   (		SCREAMING_SNAKE_CASE_							:       int   ,   SCREAMING_SNAKE_CASE_							:       list  ):
					if n < 0:
										__lowerCAmelCase            = 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            = (
										    "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   (		):
					__lowerCAmelCase            = [6, 10, 12, 15, 20, 23]
					__lowerCAmelCase            = 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            = 36

					__lowerCAmelCase            = top_down_cut_rod(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  )
					__lowerCAmelCase            = bottom_up_cut_rod(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  )
					__lowerCAmelCase            = 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()










from __future__ import annotations

from collections.abc import Iterator
from typing import Any
class     a__					:






						def __init__(     self	,    _A    ):




											"""simple docstring"""



											__lowerCAmelCase            = data
											__lowerCAmelCase            = None






class     a__					:






						def __init__(     self    ):




											"""simple docstring"""



											__lowerCAmelCase            = None
											__lowerCAmelCase            = None






						def __iter__(     self    ):




											"""simple docstring"""



											__lowerCAmelCase            = self.head
											while self.head:
																yield node.data
																__lowerCAmelCase            = node.next
																if node == self.head:
																					break






						def __len__(     self    ):




											"""simple docstring"""



											return sum(1 for _ in self    )






						def __repr__(     self    ):




											"""simple docstring"""



											return "->".join(str(_A    ) for item in iter(self    )    )






						def        __SCREAMING_SNAKE_CASE(     self	,    _A    ):




											"""simple docstring"""



											self.insert_nth(len(self    )	,    _A    )






						def        __SCREAMING_SNAKE_CASE(     self	,    _A    ):




											"""simple docstring"""



											self.insert_nth(0	,    _A    )






						def        __SCREAMING_SNAKE_CASE(     self	,    _A	,    _A    ):




											"""simple docstring"""



											if index < 0 or index > len(self    ):
																raise IndexError("list index out of range."    )
											__lowerCAmelCase            = Node(_A    )
											if self.head is None:
																__lowerCAmelCase            = new_node  # first node points itself
																__lowerCAmelCase            = __lowerCAmelCase            = new_node
											elif index == 0:  # insert at head
																__lowerCAmelCase            = self.head
																__lowerCAmelCase            = __lowerCAmelCase            = new_node
											else:
																__lowerCAmelCase            = self.head
																for _ in range(index - 1    ):
																					__lowerCAmelCase            = temp.next
																__lowerCAmelCase            = temp.next
																__lowerCAmelCase            = new_node
																if index == len(self    ) - 1:  # insert at tail
																					__lowerCAmelCase            = new_node






						def        __SCREAMING_SNAKE_CASE(     self    ):




											"""simple docstring"""



											return self.delete_nth(0    )






						def        __SCREAMING_SNAKE_CASE(     self    ):




											"""simple docstring"""



											return self.delete_nth(len(self    ) - 1    )






						def        __SCREAMING_SNAKE_CASE(     self	,    _A = 0    ):




											"""simple docstring"""



											if not 0 <= index < len(self    ):
																raise IndexError("list index out of range."    )
											__lowerCAmelCase            = self.head
											if self.head == self.tail:  # just one node
																__lowerCAmelCase            = __lowerCAmelCase            = None
											elif index == 0:  # delete head node
																__lowerCAmelCase            = self.tail.next.next
																__lowerCAmelCase            = self.head.next
											else:
																__lowerCAmelCase            = self.head
																for _ in range(index - 1    ):
																					__lowerCAmelCase            = temp.next
																__lowerCAmelCase            = temp.next
																__lowerCAmelCase            = temp.next.next
																if index == len(self    ) - 1:  # delete at tail
																					__lowerCAmelCase            = temp
											return delete_node.data






						def        __SCREAMING_SNAKE_CASE(     self    ):




											"""simple docstring"""



											return len(self    ) == 0







def 			_a   (		):
					__lowerCAmelCase            = CircularLinkedList()
					assert len(SCREAMING_SNAKE_CASE_  ) == 0
					assert circular_linked_list.is_empty() is True
					assert str(SCREAMING_SNAKE_CASE_  ) == ""

					try:
										circular_linked_list.delete_front()
										raise AssertionError  # This should not happen
					except IndexError:
										assert True  # This should happen

					try:
										circular_linked_list.delete_tail()
										raise AssertionError  # This should not happen
					except IndexError:
										assert True  # This should happen

					try:
										circular_linked_list.delete_nth(-1  )
										raise AssertionError
					except IndexError:
										assert True

					try:
										circular_linked_list.delete_nth(0  )
										raise AssertionError
					except IndexError:
										assert True

					assert circular_linked_list.is_empty() is True
					for i in range(5  ):
										assert len(SCREAMING_SNAKE_CASE_  ) == i
										circular_linked_list.insert_nth(SCREAMING_SNAKE_CASE_   ,   i + 1  )
					assert str(SCREAMING_SNAKE_CASE_  ) == "->".join(str(SCREAMING_SNAKE_CASE_  ) for i in range(1   ,   6  )  )

					circular_linked_list.insert_tail(6  )
					assert str(SCREAMING_SNAKE_CASE_  ) == "->".join(str(SCREAMING_SNAKE_CASE_  ) for i in range(1   ,   7  )  )
					circular_linked_list.insert_head(0  )
					assert str(SCREAMING_SNAKE_CASE_  ) == "->".join(str(SCREAMING_SNAKE_CASE_  ) for i in range(0   ,   7  )  )

					assert circular_linked_list.delete_front() == 0
					assert circular_linked_list.delete_tail() == 6
					assert str(SCREAMING_SNAKE_CASE_  ) == "->".join(str(SCREAMING_SNAKE_CASE_  ) for i in range(1   ,   6  )  )
					assert circular_linked_list.delete_nth(2  ) == 3

					circular_linked_list.insert_nth(2   ,   3  )
					assert str(SCREAMING_SNAKE_CASE_  ) == "->".join(str(SCREAMING_SNAKE_CASE_  ) for i in range(1   ,   6  )  )

					assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
					import doctest

					doctest.testmod()




