Skip to main content

周赛 Weekly Contest 401

https://leetcode.cn/contest/weekly-contest-401/

100325. Find the Child Who Has the Ball After K Seconds​

class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        i = 0
        d = 1
        while k > 0:
            if d == 1:
                if i == n-1:
                    i = n-2
                    d = 0
                else:
                    i += 1
            else:
                if i == 0:
                    i = 1
                    d = 1
                else:
                    i -= 1
            k -= 1
        return i

100305. Find the N-th Value After K Seconds​

class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        a = [1 for i in range(n)]
        for _ in range(k):
            for i in range(1, n, 1):
                a[i] += a[i-1] 
        return a[n-1] % (10**9 + 7)

100319. Maximum Total Reward Using Operations I​

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues = sorted(list(set(rewardValues)))
        @cache
        def traceback(x, startI):
            maxX = x
            pre = -1
            i2 = startI
            j2 = len(rewardValues)-1
            while i2 + 1 < j2:
                mid = (i2 + j2) // 2
                if rewardValues[mid] <= x:
                    i2 = mid
                else:
                    j2 = mid
            
            for i in range(i2, len(rewardValues), 1):
                if rewardValues[i] > x:
                    if pre == -1:
                        pre = rewardValues[i]
                    else:
                        if i < len(rewardValues)-2 and x + rewardValues[i] > rewardValues[i+1]:
                            break
                        pre = rewardValues[i]

                    tmp = rewardValues[i]
                    # print(i, rewardValues, tmp,"next", pre, x, maxX)
                    maxX = max(maxX, traceback(x+tmp, i+1))
            return maxX
        return traceback(0, 0)

100320. Maximum Total Reward Using Operations II​

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues = sorted(list(set(rewardValues)))

        def traceback(x, startI):
            maxX = x
            pre = -1
            i2 = startI
            j2 = len(rewardValues)-1
            while i2 + 1 < j2:
                mid = (i2 + j2) // 2
                if rewardValues[mid] <= x:
                    i2 = mid
                else:
                    j2 = mid
            
            for i in range(i2, len(rewardValues), 1):
                if rewardValues[i] > x:
                    # if pre == -1:
                    #     pre = rewardValues[i]
                    # else:
                    #     if pre + x < rewardValues[i]:
                    #         # print("break", i, pre, x, maxX)
                    #         break
                    #     pre = rewardValues[i]
                    
                    tmp = rewardValues[i]
                    # print(i, rewardValues, tmp,"next", pre, x, maxX)
                    maxX = max(maxX, traceback(x+tmp, i+1))
            return maxX
        return traceback(0, 0)