In our system, we have a pipeline consisting of data processing units, each with varying throughputs as represented by throughput[i]. These units are arranged in a series, requiring data to pass through each of them sequentially. Consequently, the total throughput of the pipeline is constrained by the unit with the smallest throughput, which becomes the bottleneck.

Each service can be scaled up independently, with the cost of scaling up the i-th service one unit equal to scaling_cost[i]. After scaling up a service x times, it can process throughput[i] × (1 + x) messages per minute.

Given arrays throughput[n], scaling_cost[n], integer budget, and integer n, determine the optimal scaling configuration so that the throughput generated by the n-th service is maximized. Return that max throughput.

Example: throughput = [4,2,7], scaling_cost = [3,5,6], budget = 32 → 10.

解法

对答案 T 二分：吞吐 T 可行当且仅当 sum((ceil(T/tp[i]) - 1) * sc[i]) ≤ budget。搜索区间 [min(tp), max(tp) * (budget/min_cost + 1)]。复杂度 O(n log(max_T))。

def get_maximum_throughput(tp, sc, budget, n):
    lo, hi, min_cost = min(tp), max(tp), min(sc)
    hi = hi * (budget // min_cost + 1) + 1

    def feasible(T):
        cost = 0
        for i in range(n):
            need = max(0, (T + tp[i] - 1) // tp[i] - 1)
            cost += sc[i] * need
            if cost > budget:
                return False
        return True

    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

class Solution {
    static long getMaximumThroughput(int[] tp, int[] sc, long budget, int n) {
        long lo = Long.MAX_VALUE, hi = 0, minCost = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            lo = Math.min(lo, tp[i]);
            hi = Math.max(hi, tp[i]);
            minCost = Math.min(minCost, sc[i]);
        }
        hi = hi * (budget / minCost + 1) + 1;
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;
            if (feasible(tp, sc, n, mid, budget)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    static boolean feasible(int[] tp, int[] sc, int n, long T, long budget) {
        long cost = 0;
        for (int i = 0; i < n; i++) {
            long need = Math.max(0, (T + tp[i] - 1) / tp[i] - 1);
            cost += (long) sc[i] * need;
            if (cost > budget) return false;
        }
        return true;
    }
}

bool feasible(vector<int>& tp, vector<int>& sc, int n, long long T, long long budget) {
 long long cost = 0;
 for (int i = 0; i < n; i++) {
 long long need = max(0LL, (T + tp[i] - 1) / tp[i] - 1);
 cost += (long long)sc[i] * need;
 if (cost > budget) return false;
 }
 return true;
}

long long getMaximumThroughput(vector<int>& tp, vector<int>& sc, long long budget, int n) {
 long long lo = *min_element(tp.begin(), tp.end());
 long long hi = *max_element(tp.begin(), tp.end());
 long long minCost = *min_element(sc.begin(), sc.end());
 hi = hi * (budget / minCost + 1) + 1;
 while (lo < hi) {
 long long mid = lo + (hi - lo + 1) / 2;
 if (feasible(tp, sc, n, mid, budget)) lo = mid;
 else hi = mid - 1;
 }
 return lo;
}

The agency is giving you an int num named N and an arr of ints called arr[n]. Ur task -

• 1. Find two nums with indices a & b (where b > a)
• 2. Figure out the toal of the two nums
• 3. Make sure the total is divisible by N
• Finally, return the number of special pairs that meet the criteria outlined in tasks 1 through 3

Constraints

• 1 ≤ N ≤ 10⁹
• 1 ≤ len of arr ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹

Example 1

Input:

N = 3
arr = [5, 4, 3, 2, 1]

Output:

4

Explanation: We can that there are FOUR pairs that meet the criteria outlined in task 1 through task 3 above arr[0] + arr[1] = 1 + 2 = 3, 3 3 = 1 arr[0] + arr[4] = 1 + 5 = 6, 6 3 = 2 arr[1] + arr[3] = 2 + 4 = 6, 6 3 = 2 arr[3] + arr[4] = 4 + 5 = 9, 9 3 = 3 So, 4 should be returned. For original prompt, pls refer source image.

解法

用计数：对每个 r ∈ [0, N) 统计 arr[i] % N == r 的个数。配对 (a, b) 满足 (arr[a] + arr[b]) % N == 0 ⇔ arr[b] % N == (N - arr[a] % N) % N。r == 0 自配对 C(cnt[0], 2)；其它 r ≠ N/2：cnt[r] * cnt[N-r]；r == N/2(N 偶数)：C(cnt[N/2], 2)。注意只配对一次。复杂度 O(n)。

from typing import List
from collections import Counter

def nums_that_can_be_divided_by_n(N: int, arr: List[int]) -> int:
    mod_cnt = Counter(x % N for x in arr)
    total = 0
    keys = list(mod_cnt.keys())
    for r in mod_cnt:
        if r == 0:
            c = mod_cnt[r]
            total += c * (c - 1) // 2
        elif 2 * r == N:
            c = mod_cnt[r]
            total += c * (c - 1) // 2
        elif r < N - r:
            total += mod_cnt[r] * mod_cnt.get(N - r, 0)
    return total

import java.util.*;

class Solution {
    long numsThatCanBeDividedByN(int N, int[] arr) {
        long[] mod = new long[N];
        for (int x : arr) mod[x % N]++;
        long total = 0;
        for (int r = 0; r < N; r++) {
            if (r == 0 || 2 * r == N) total += mod[r] * (mod[r] - 1) / 2;
            else if (r < N - r) total += mod[r] * mod[N - r];
        }
        return total;
    }
}

class Solution {
public:
    long long numsThatCanBeDividedByN(int N, vector<int>& arr) {
        vector<long long> mod(N, 0);
        for (int x : arr) mod[x % N]++;
        long long total = 0;
        for (int r = 0; r < N; r++) {
            if (r == 0 || 2 * r == N) total += mod[r] * (mod[r] - 1) / 2;
            else if (r < N - r) total += mod[r] * mod[N - r];
        }
        return total;
    }
};

Sup ! This time the agency will give you:

• An int 2D arr
• A position within the input 2D arr
• A so called replacing val What they want you to do: Replace the val at the starting position with the provided replacing val. Repeat this process for all positions connected to the starting position via sides with the same val as the starting position.

Constraints

• 1 ≤ arr.length, arr[0].length ≤ 1000
• 0 ≤ arr[i][j] ≤ 10^9
• 0 ≤ pos[0] < arr.length，0 ≤ pos[1] < arr[0].length
• 0 ≤ replacingVal ≤ 10^9

Example 1

Input:

replacingVal = 2
arr = [[0, 1, 0, 0, 0], [1, 1, 1, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 1, 0]]
pos = [1, 2]

Output:

[[0, 2, 0, 0, 0], [2, 2, 2, 0, 0], [2, 2, 0, 0, 0], [0, 2, 0, 1, 0]]

Explanation: No explanation is provided for now. For original prompt, pls refer source image.

解法

经典 floodfill：BFS / DFS 从起点向 4 邻居扩散，把相同原值的位置替换为新值。若新值等于原值直接返回。复杂度 O(rows · cols)。

from typing import List
from collections import deque

def replacing_num(replacingVal: int, arr: List[List[int]], pos: List[int]) -> List[List[int]]:
    if not arr or not arr[0]:
        return arr
    r0, c0 = pos
    old = arr[r0][c0]
    if old == replacingVal:
        return arr
    rows, cols = len(arr), len(arr[0])
    q = deque([(r0, c0)])
    arr[r0][c0] = replacingVal
    while q:
        r, c = q.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and arr[nr][nc] == old:
                arr[nr][nc] = replacingVal
                q.append((nr, nc))
    return arr

import java.util.*;

class Solution {
    int[][] replacingNum(int replacingVal, int[][] arr, int[] pos) {
        if (arr.length == 0) return arr;
        int r0 = pos[0], c0 = pos[1];
        int old = arr[r0][c0];
        if (old == replacingVal) return arr;
        int rows = arr.length, cols = arr[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{r0, c0});
        arr[r0][c0] = replacingVal;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && arr[nr][nc] == old) {
                    arr[nr][nc] = replacingVal;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        return arr;
    }
}

class Solution {
public:
    vector<vector<int>> replacingNum(int replacingVal, vector<vector<int>> arr, vector<int> pos) {
        if (arr.empty()) return arr;
        int r0 = pos[0], c0 = pos[1];
        int old = arr[r0][c0];
        if (old == replacingVal) return arr;
        int rows = arr.size(), cols = arr[0].size();
        queue<pair<int, int>> q;
        q.push({r0, c0});
        arr[r0][c0] = replacingVal;
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && arr[nr][nc] == old) {
                    arr[nr][nc] = replacingVal;
                    q.push({nr, nc});
                }
            }
        }
        return arr;
    }
};

Given two integers y and x, compute y /

Constraints

• x ≠ 0
• Use two digits after the decimal point in the returned string.

Example 1

Input:

y = 10
x = 2

Output:

"5.00"

Explanation: 10 / 2 = 5, formatted to two decimal places as 5.00.

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Problem: Piecewise Linear Interpolation and Extrapolation for a Polyline You are given a set of 2D points [(x1,y1), (x2,y2), ..., (xn,yn)]. After sorting points by increasing x, connect consecutive points with straight line segments to form a polyline. For each query xq, output the corresponding yq on this polyline: If xq lies between two adjacent points xi ≤ xq ≤ xi+1, perform linear interpolation on that segment. If xq < x1, extrapolate by extending the leftmost segment ((x1,y1)–(x2,y2)). If xq > xn, extrapolate by extending the rightmost segment ((x_{n-1},y_{n-1})–(xn,yn)). If xq equals some xi, return yi exactly. Input (stdin) First line: two integers n q (#points, #queries) Next n lines: two real numbers x y Next q lines: one real number xq Output (stdout) For each query print one line yq (floating-point; 1e-6 error tolerated). Constraints 2 ≤ n ≤ 2e5 1 ≤ q ≤ 2e5 Points may be unsorted; sort them. After sorting, all x are strictly increasing. Target overall complexity: O((n+q) log n). Formula Given (xa,ya) and (xb,yb) (xa ≠ xb): y(x) = ya + (yb - ya) * (x - xa) / (xb - xa) Function Description Complete solvePiecewiseLinearInterpolation. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

A sewer drainage system forms a rooted tree. Water enters at n nodes numbered from 0 to n - 1 and flows upward to the root 0. The tree is described by parent, where parent[i] = j means water flows from node i to its direct parent j. The root has parent[0] = -1. input[i] is the amount of water entering directly at node i. The total flow through a node is its own direct input plus the total flows of all of its children. Cut exactly one branch so the tree is split into two subtrees. Return the minimum possible absolute difference between the total flows of the two resulting parts. Function Description Complete drainagePartition. drainagePartition has the following parameters:

• int[] parent: the parent array describing the rooted tree
• int[] input: direct inflow at each node Returns: int minimum absolute difference after cutting one branch.

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ input[i] ≤ 10⁴
• parent[0] = -1
• 0 ≤ parent[i] < i for 1 ≤ i < n
• The tree depth is at most 500.

Example 1

Input:

parent = [-1,0,0,1,1,2]
input = [1,2,2,1,1,1]

Output:

0

Explanation: Cut the edge between nodes 1 and 0. One component has nodes {0,2,5} with total flow 4, and the other has nodes {1,3,4} with total flow 4. The difference is 0.

Example 2

Input:

parent = [-1,0,1,2]
input = [1,4,3,4]

Output:

2

Explanation: Cut the edge between nodes 1 and 2. The two resulting parts have total flows 5 and 7, so the minimum difference is 2.