BakerHub

# A. Divide a String Into Groups of Size k (opens new window)

Iterate over the array, cut every k characters into a word. For the last word made in this way, if its length is less than k, fill the needed length with character fill.

DETAILS 
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> ans;
        string curr = "";
        for (int i = 0; i < s.size(); ++i) {
            if (i % k == 0 && i != 0) {
                ans.push_back(curr);
                curr = s[i];
            } else {
                curr.push_back(s[i]);
            }
        }
        if (curr.size() > 0) {
            int curLen = curr.size();
            while (curLen < k) {
                curr.push_back(fill);
                curLen += 1;
            }
            ans.push_back(curr);
        }
        
        return ans;        
    }

# B. Minimum Moves to Reach Target Score (opens new window)

Operation double must apply on the maximum possible numbers, thus we can reach the target score using mumimum moves. We can solve this problem backward, that is:

  • from target to start.
  • double to half
  • plus 1 to minus 1 If the current target is even and we still have double operations, we cut the target by half. Otherwise, we minus target by 1.
DETAILS 
public:
    int minMoves(int target, int maxDoubles) {
        int ans = 0;
        while (target > 1 && maxDoubles > 0) {
            if (target % 2 == 1) {
                target -= 1;
            } else {
                target /= 2;
                maxDoubles -= 1;
            }            
            ans += 1;
        }        
        return ans + (target - 1);
        
    }

# C. Solving Questions With Brainpower (opens new window)

Dynamic Programming.

DETAILS 
def mostPoints(self, A: List[List[int]]) -> int:        
        n = len(A)
        if n == 1: 
            return A[0][0]    
        dp = [0] * (n - 1) + [A[-1][0]] 
        for i in range(n - 2, -1, -1):            
            p, t = A[i]
            if i + t < n - 1:
                p += dp[i + t + 1]
            dp[i] = max(p, dp[i + 1])
            
        return dp[0]

# D. Maximum Running Time of N Computers (opens new window)

把电池按照电量排序，只看【电量最大的后n节电池】，把前面的小电池等效为一块电池【outer】。 在这N块电池里，从小到大遍历（【0】【1】【2】... 【n-1】：

  • 假设我们把【outer】的全部电量都给【0】号电池：
  • 如果【0】的电量仍然不够【1】号电池的电量，说明系统最大的运行时间就是【0】+【outer】
  • 否则，我们把【outer】的电量匀出一部分给【0】，使其等于【1】号电量；
  • 接下来，我们看【outer】剩下的电量，均分给【0】和【1】，看他俩的电量够不够【2】号电池的电量。
  • 如果【0】【1】的电量不够【2】号电量，说明系统最大运行时间是 （【1】+【2】+【outer】）/2,
  • 否则，我们把【outer】的电量均出一部分给【0】和【1】，使其等于【2】号电量。
  • ....直到分完电量，或者走到最后一块电池【n-1】
DETAILS 
def maxRunTime(self, n: int, A: List[int]) -> int:
        A.sort()
        outer, ans, presum = sum(A[:-n]), 0, 0
        A = A[-n:]

        for i, x in enumerate(A[:-1]): 
            presum += x 
            if A[i + 1] * (i + 1) - presum > outer: 
                return (presum + outer) // (i + 1)
        return (presum + A[-1] + outer) // n

← Weekly Contest 275 →