


from __future__ import annotations







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(     self		,				_UpperCAmelCase		,				_UpperCAmelCase ):
       snake_case_	,   snake_case_	=				text, pattern
       snake_case_	,   snake_case_	=				len(_UpperCAmelCase ), len(_UpperCAmelCase )



 def 						UpperCamelCase__					(     self		,				_UpperCAmelCase ):

       for i in range(self.patLen - 1		,				-1		,				-1 ):
             if char == self.pattern[i]:
                   return i
       return -1



 def 						UpperCamelCase__					(     self		,				_UpperCAmelCase ):

       for i in range(self.patLen - 1		,				-1		,				-1 ):
             if self.pattern[i] != self.text[current_pos + i]:
                   return current_pos + i
       return -1





 def 						UpperCamelCase__					(     self ):
       # searches pattern in text and returns index positions
       snake_case_	=				[]
       for i in range(self.textLen - self.patLen + 1 ):
             snake_case_	=				self.mismatch_in_text(_UpperCAmelCase )
             if mismatch_index == -1:
                   positions.append(_UpperCAmelCase )
             else:
                   snake_case_	=				self.match_in_pattern(self.text[mismatch_index] )
                   snake_case_	=				(
                       mismatch_index - match_index
                   )  # shifting index lgtm [py/multiple-definition]
       return positions





UpperCAmelCase      =   """ABAABA"""
UpperCAmelCase      =   """AB"""
UpperCAmelCase      =   BoyerMooreSearch(text, pattern)
UpperCAmelCase      =   bms.bad_character_heuristic()

if len(positions) == 0:
   print("""No match found""")
else:
   print("""Pattern found in following positions: """)
   print(positions)



def 	__lowerCAmelCase   (SCREAMING_SNAKE_CASE , SCREAMING_SNAKE_CASE )->  list[int]:




      """simple docstring"""

      snake_case_	=				int(SCREAMING_SNAKE_CASE )

      # Initialize Result
      snake_case_	=				[]

      # Traverse through all denomination
      for denomination in reversed(SCREAMING_SNAKE_CASE ):
            # Find denominations
            while int(SCREAMING_SNAKE_CASE ) >= int(SCREAMING_SNAKE_CASE ):
                  total_value -= int(SCREAMING_SNAKE_CASE )
                  answer.append(SCREAMING_SNAKE_CASE )  # Append the "answers" array

      return answer


# Driver Code
if __name__ == "__main__":
   UpperCAmelCase      =   []
   UpperCAmelCase      =   """0"""

   if (
       input("""Do you want to enter your denominations ? (yY/n): """).strip().lower()
       == "y"
   ):
      UpperCAmelCase      =   int(input("""Enter the number of denominations you want to add: """).strip())

      for i in range(0, n):
         denominations.append(int(input(f'''Denomination {i}: ''').strip()))
      UpperCAmelCase      =   input("""Enter the change you want to make in Indian Currency: """).strip()
   else:
      # All denominations of Indian Currency if user does not enter
      UpperCAmelCase      =   [1, 2, 5, 10, 20, 50, 100, 500, 2000]
      UpperCAmelCase      =   input("""Enter the change you want to make: """).strip()

   if int(value) == 0 or int(value) < 0:
      print("""The total value cannot be zero or negative.""")

   else:
      print(f'''Following is minimal change for {value}: ''')
      UpperCAmelCase      =   find_minimum_change(denominations, value)
      # Print result
      for i in range(len(answer)):
         print(answer[i], end=""" """)