class Solution:
    def distMoney(self, money: int, children: int) -> int:
        if money < children: return -1
        money -= children # 每人至少 1 美元
        res = min(money // 7, children) # 初步分配，让尽量多的人分到 8 美元
        money -= res * 7
        children -= res
        if (children == 0 and money > 0) or (children == 1 and money == 3):
            res -= 1
        return res

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        a = b = inf
        for x in prices:
            if x < a:
                b, a = a, x
            elif x < b:
                b = x
        return money - a - b if a + b <= money else money

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 1, n
        while l <= r:
            mid = l + r >> 1
            if guess(mid) == 1: l = mid + 1
            elif guess(mid) == -1: r = mid - 1
            else: return mid

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        res = acc = 0
        for x in gain:
            acc += x
            if acc > res: res = acc
        return res

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        ans, acc = 1, 0
        for x in nums:
            acc += x
            if acc < 0:
                ans = max(ans, 1 - acc)
        return ans

class Solution:
    def smallestEqual(self, nums: List[int]) -> int:
        for i, x in enumerate(nums):
            if i % 10 == x: return i
        return -1

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:        
        # odd = even = 0
        # for k in position:
        #     if k % 2: odd += 1
        #     else: even += 1
        # return min(even, odd)
        
        # d = [0, 0]
        # for i in position: d[i%2] += 1
        # return min(d)

        return min(x := sum(i & 1 for i in position), len(position) - x)

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:       
        if destination < start: # 交换出发点和目的地距离相等
            start, destination = destination, start            
        d = sum(distance[start : destination]) # 出发点到目的地距离
        return min(d, sum(distance) - d)

class Solution:
    def smallestEqual(self, nums: List[int]) -> int:
        for i, x in enumerate(nums):
            if i % 10 == x: return i
        return -1

class Solution:
    def averageValue(self, nums: List[int]) -> int:
        sum = count = 0
        for x in nums:
            if x % 6 == 0:
                sum += x
                count += 1
        return 0 if count == 0 else sum // count

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        res = 0   # 两栋颜色不同房子的最远距离
        # 遍历两栋房子下标并维护最远距离
        for i in range(n):
            for j in range(i + 1, n):
                if colors[i] != colors[j]:
                    res = max(res, j - i)
        return res

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        c = colors[0]
        if c != colors[-1]: return n - 1
        i, j = 1, n - 2
        while colors[i] == c: i += 1
        while colors[j] == c: j -= 1
        return max(j, n - i - 1)

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        n = len(tickets)
        res = 0
        for i in range(n):
            # 遍历计算每个人所需时间
            if i <= k:
                res += min(tickets[i], tickets[k])
            else:
                res += min(tickets[i], tickets[k] - 1)
        return res

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        res = inf
        for i, x in enumerate(nums):
            if x == target:
                res = min(res, abs(i - start))
        return res