






"""simple docstring"""




def 			lowerCAmelCase__     (     ):



  '''simple docstring'''
  return [list(range(1_0_0_0 - i     ,   -1_0_0_0 - i     ,   -1				)				) for i in range(1_0_0_0				)]


_snake_case          =   generate_large_matrix()
_snake_case          =   (
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)

def 			lowerCAmelCase__     (     UpperCamelCase__				):



  '''simple docstring'''
  assert all(row == sorted(__snake_case     ,   reverse=__snake_case				) for row in grid				)
  assert all(list(__snake_case				) == sorted(__snake_case     ,   reverse=__snake_case				) for col in zip(*__snake_case				)				)

def 			lowerCAmelCase__     (     UpperCamelCase__				):



  '''simple docstring'''
  _a  :       int             =	0
  _a  :       List[Any]             =	len(__snake_case				) - 1

  # Edge cases such as no values or all numbers are negative.
  if not array or array[0] < 0:
    return 0

  while right + 1 > left:
    _a  :       Any             =	(left + right) // 2
    _a  :       Union[str, Any]             =	array[mid]

    # Num must be negative and the index must be greater than or equal to 0.
    if num < 0 and array[mid - 1] >= 0:
      return mid

    if num >= 0:
      _a  :       List[Any]             =	mid + 1
    else:
      _a  :       Tuple             =	mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
  return len(__snake_case				)

def 			lowerCAmelCase__     (     UpperCamelCase__				):



  '''simple docstring'''
  _a  :       List[Any]             =	0
  _a  :       Union[str, Any]             =	len(grid[0]				)

  for i in range(len(__snake_case				)				):
    _a  :       Optional[int]             =	find_negative_index(grid[i][:bound]				)
    total += bound
  return (len(__snake_case				) * len(grid[0]				)) - total

def 			lowerCAmelCase__     (     UpperCamelCase__				):



  '''simple docstring'''
  return len([number for row in grid for number in row if number < 0]				)

def 			lowerCAmelCase__     (     UpperCamelCase__				):



  '''simple docstring'''
  _a  :       List[Any]             =	0
  for row in grid:
    for i, number in enumerate(__snake_case				):
      if number < 0:
        total += len(__snake_case				) - i
        break
  return total

def 			lowerCAmelCase__     (     ):



  '''simple docstring'''
  from timeit import timeit

  print("""Running benchmarks"""				)
  _a  :       int             =	(
      "from __main__ import count_negatives_binary_search, "
      "count_negatives_brute_force, count_negatives_brute_force_with_break, grid"
  )
  for func in (
      "count_negatives_binary_search",  # took 0.7727 seconds
      "count_negatives_brute_force_with_break",  # took 4.6505 seconds
      "count_negatives_brute_force",  # took 12.8160 seconds
  ):
    _a  :       Optional[int]             =	timeit(F"""{func}(grid=grid)"""     ,   setup=__snake_case     ,   number=5_0_0				)
    print(F"""{func}() took {time:0.4f} seconds"""				)


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 benchmark()






"""simple docstring"""






from __future__ import annotations

import time

import numpy as np

__snake_case							:   Optional[Any]      =    [8, 5, 9, 7]
__snake_case							:   List[Any]      =    [
    [2, 0, 1, 1],
    [0, 1, 2, 1],
    [4, 0, 0, 3],
    [0, 2, 1, 0],
    [1, 0, 3, 0],
]
__snake_case							:   Optional[int]      =    [
    [3, 2, 1, 4],
    [0, 2, 5, 2],
    [5, 1, 0, 5],
    [1, 5, 3, 0],
    [3, 0, 3, 3],
]



class 			A__   :




	'''simple docstring'''





	def __init__(     self:		Any       ,			_SCREAMING_SNAKE_CASE:		list[int]       ,			_SCREAMING_SNAKE_CASE:		list[list[int]]       ,			_SCREAMING_SNAKE_CASE:		list[list[int]]       ,			)				->       None:

				"""simple docstring"""

				__lowerCAmelCase      :  Any												=       claim_vector
				__lowerCAmelCase      :  Tuple												=       allocated_resources_table
				__lowerCAmelCase      :  Tuple												=       maximum_claim_table

	def 							_SCREAMING_SNAKE_CASE   (     self:		Union[str, Any])				->       list[int]:

				"""simple docstring"""

				return [
				    sum(p_item[i] for p_item in self.__allocated_resources_table)
				    for i in range(len(self.__allocated_resources_table[0]))
				]

	def 							_SCREAMING_SNAKE_CASE   (     self:		int)				->       list[int]:

				"""simple docstring"""

				return np.array(self.__claim_vector) - np.array(
				    self.__processes_resource_summation())

	def 							_SCREAMING_SNAKE_CASE   (     self:		int)				->       list[list[int]]:

				"""simple docstring"""

				return [
				    list(np.array(self.__maximum_claim_table[i]) - np.array(_SCREAMING_SNAKE_CASE))
				    for i, allocated_resource in enumerate(self.__allocated_resources_table)
				]

	def 							_SCREAMING_SNAKE_CASE   (     self:		List[Any])				->       dict[int, list[int]]:

				"""simple docstring"""

				return {self.__need().index(_SCREAMING_SNAKE_CASE): i for i in self.__need()}

	def 							_SCREAMING_SNAKE_CASE   (     self:		Optional[Any]       ,			**_SCREAMING_SNAKE_CASE:		List[Any])				->       None:

				"""simple docstring"""

				__lowerCAmelCase      :  Optional[int]												=       self.__need()
				__lowerCAmelCase      :  int												=       self.__allocated_resources_table
				__lowerCAmelCase      :  Dict												=       self.__available_resources()
				__lowerCAmelCase      :  str												=       self.__need_index_manager()
				for kw, val in kwargs.items():
							if kw and val is True:
										self.__pretty_data()
				print("_" * 50 + "\n")
				while need_list:
							__lowerCAmelCase      :  int												=       False
							for each_need in need_list:
										__lowerCAmelCase      :  Dict												=       True
										for index, need in enumerate(_SCREAMING_SNAKE_CASE):
													if need > available_resources[index]:
																__lowerCAmelCase      :  Dict												=       False
																break
										if execution:
													__lowerCAmelCase      :  Any												=       True
													# get the original index of the process from ind_ctrl db
													for original_need_index, need_clone in need_index_manager.items():
																if each_need == need_clone:
																			__lowerCAmelCase      :  Union[str, Any]												=       original_need_index
													print(F"""Process {process_number + 1} is executing.""")
													# remove the process run from stack
													need_list.remove(_SCREAMING_SNAKE_CASE)
													# update available/freed resources stack
													__lowerCAmelCase      :  Dict												=       np.array(_SCREAMING_SNAKE_CASE) + np.array(
													    alloc_resources_table[process_number])
													print(
													    "Updated available resource stack for processes: "
													    + " ".join([str(_SCREAMING_SNAKE_CASE) for x in available_resources]))
													break
							if safe:
										print("The process is in a safe state.\n")
							else:
										print("System in unsafe state. Aborting...\n")
										break







	def 							_SCREAMING_SNAKE_CASE   (     self:		Union[str, Any])				->       List[Any]:

				"""simple docstring"""

				print(" " * 9 + "Allocated Resource Table")
				for item in self.__allocated_resources_table:
							print(
							    F"""P{self.__allocated_resources_table.index(_SCREAMING_SNAKE_CASE) + 1}"""
							    + " ".join(F"""{it:>8}""" for it in item)
							    + "\n")
				print(" " * 9 + "System Resource Table")
				for item in self.__maximum_claim_table:
							print(
							    F"""P{self.__maximum_claim_table.index(_SCREAMING_SNAKE_CASE) + 1}"""
							    + " ".join(F"""{it:>8}""" for it in item)
							    + "\n")
				print(
				    "Current Usage by Active Processes: "
				    + " ".join(str(_SCREAMING_SNAKE_CASE) for x in self.__claim_vector))
				print(
				    "Initial Available Resources:       "
				    + " ".join(str(_SCREAMING_SNAKE_CASE) for x in self.__available_resources()))
				time.sleep(1)


if __name__ == "__main__":
	import doctest

	doctest.testmod()