Appearance
question:A company has a warehouse full of boxes, and each box is labeled with a unique integer. They need to stack these boxes such that they form a tower with the maximum possible height, but there is a constraint: a box can only be placed on top of another if the label of the box on top is divisible by the label of the box below it. You are required to help the company find out the maximum possible height of the tower. Each box weighs the same, so the only constraint is based on the integer labels. Given an array representing the labels of the boxes, determine the maximum number of boxes that can be stacked following the rule. Function Description Complete the `maxTowerHeight` function in the editor below. `maxTowerHeight` has the following parameter: - `int boxLabels[n]`: an array of integers representing the labels of the boxes Returns - `int`: the maximum height of the tower that can be formed Input Format The first line contains an integer `n`, the number of boxes in the warehouse. The second line contains `n` space-separated integers, representing the labels of the boxes. Constraints 1 leq n leq 50 1 leq text{boxLabels}[i] leq 10^9 Sample Input 0 6 1 3 6 2 4 12 Sample Output 0 4 Explanation 0 One possible stacking strategy is: - Place box with label `1` at the bottom - Place box with label `2` on top (2 is divisible by 1) - Place box with label `4` on top (4 is divisible by 2) - Place box with label `12` on top (12 is divisible by 4) This forms a valid tower with height 4. We cannot form a taller tower with the given labels. Another example of a valid sequence would be `1-3-6-12`, but it also gives a maximum height of 4. Therefore, the maximum height possible is 4.
answer:def maxTowerHeight(boxLabels): boxLabels.sort() n = len(boxLabels) dp = [1] * n for i in range(n): for j in range(i): if boxLabels[i] % boxLabels[j] == 0: dp[i] = max(dp[i], dp[j] + 1) return max(dp)
question:Given an array of integers, you are tasked with finding the maximum sum of a contiguous subarray with the constraint that the subarray must have at least one positive number. This problem is a twist on the classic "maximum subarray" problem, adding the additional challenge of ensuring that the subarray includes positive numbers. -----Input----- The first line contains a single integer n (1 leq n leq 100,000), which represents the size of the array. The second line contains n integers a_1, a_2, ldots, a_n (-10^4 leq a_i leq 10^4), which represent the elements of the array. -----Output----- Output a single integer, the maximum sum of a contiguous subarray that includes at least one positive number. If there are no positive numbers in the array, output the largest negative number from the array. -----Examples----- Input 8 -2 -3 4 -1 -2 1 5 -3 Output 7 Input 5 -3 -2 -1 -4 -5 Output -1 -----Note----- In the first example, the subarray [4, -1, -2, 1, 5] provides the maximum sum of 7, which includes positive numbers. In the second example, as there are no positive numbers in the array, the largest single negative number, which is -1, is outputted.
answer:def max_subarray_with_positive(nums): Returns the maximum sum of a contiguous subarray that includes at least one positive number. If the array contains no positive number, returns the largest negative number. :param nums: List of integers representing the array. :return: Maximum sum of a valid subarray. # Early exit when there's no positive number in the array if all(num <= 0 for num in nums): return max(nums) max_current, max_global = 0, float('-inf') for num in nums: max_current += num if max_current > max_global: max_global = max_current if max_current < 0: max_current = 0 return max_global
question:You are given a sequence of integers. Your task is to rearrange the sequence such that the difference between any two adjacent integers is minimized. If there are multiple valid arrangements, you can output any of them. -----Input----- The input consists of multiple test cases. The first line contains an integer t (1 leq t leq 500) — the number of test cases. The descriptions of the test cases follow. The first line of each test case contains a single integer n (2 leq n leq 10^5) — the length of the sequence. The following line contains n space-separated integers a_1, a_2, ldots, a_n (-10^9 leq a_i leq 10^9) — the elements of the sequence. It is guaranteed that the sum of n over all test cases does not exceed 5 cdot 10^5. -----Output----- For each test case, output any rearranged sequence such that the difference between any two adjacent integers is minimized. -----Examples----- Input 3 5 4 2 1 3 5 4 -1 -2 -3 -4 3 2 1001 1000 Output 1 2 3 4 5 -4 -3 -2 -1 1000 1001 2 -----Note----- In the first test case, one possible arrangement is [1, 2, 3, 4, 5], where the difference between any adjacent integers is 1. In the second test case, one possible arrangement is [-4, -3, -2, -1], where the difference between any adjacent integers is 1. In the third test case, one possible arrangement is [1000, 1001, 2], where the differences between adjacent integers are minimized (1 and 999).
answer:def rearrange_to_minimize_diff(test_cases): results = [] for case in test_cases: n, sequence = case sequence.sort() results.append(sequence) return results def parse_input(input_str): lines = input_str.strip().split('n') t = int(lines[0]) test_cases = [] index = 1 for _ in range(t): n = int(lines[index]) sequence = list(map(int, lines[index + 1].split())) test_cases.append((n, sequence)) index += 2 return test_cases def format_output(results): return "n".join(" ".join(map(str, seq)) for seq in results) # Main function to handle input and output def main(input_str): test_cases = parse_input(input_str) results = rearrange_to_minimize_diff(test_cases) return format_output(results)
question:You are given an undirected graph with N nodes and M edges. Each edge in the graph has a weight. Let g(i) be a function that returns the sum of the weights of all edges connected to node i. You need to find the values of g(1), g(2), ..., g(N). ------ Input Format ------ - The first line contains a single integer T, denoting the number of test cases. - Each test case consists of multiple lines of input. - The first line of each test case contains two integers N and M denoting the number of nodes and the number of edges respectively. - The next M lines each contain three integers u, v, and w denoting an edge between nodes u and v with weight w. ------ Output Format ------ For each test case, output on a new line N space-separated integers, the values of g(1), g(2), ..., g(N). ------ Constraints ------ 1 ≤ T ≤ 100 1 ≤ N ≤ 10^{5} 0 ≤ M ≤ 10^{6} 1 ≤ u, v ≤ N 1 ≤ w ≤ 10^{5} ------ Sample Input ------ 2 3 3 1 2 4 2 3 5 1 3 7 4 2 1 2 10 3 4 20 ------ Sample Output ------ 11 9 12 10 10 20 20 ------ Explanation ------ Test case 1: - Node 1 has edges with weights 4 and 7 connected to nodes 2 and 3 respectively, so g(1) = 4 + 7 = 11. - Node 2 has edges with weights 4 and 5 connected to nodes 1 and 3 respectively, so g(2) = 4 + 5 = 9. - Node 3 has edges with weights 5 and 7 connected to nodes 2 and 1 respectively, so g(3) = 5 + 7 = 12. Test case 2: - Node 1 has an edge with weight 10 connected to node 2, so g(1) = 10. - Node 2 has an edge with weight 10 connected to node 1, so g(2) = 10. - Node 3 has an edge with weight 20 connected to node 4, so g(3) = 20. - Node 4 has an edge with weight 20 connected to node 3, so g(4) = 20.
answer:def compute_edge_sums(T, test_cases): results = [] for case in test_cases: N, M, edges = case edge_sums = [0] * N for (u, v, w) in edges: edge_sums[u-1] += w edge_sums[v-1] += w results.append(edge_sums) return results def parse_input_and_compute_sums(input_string): lines = input_string.strip().split("n") T = int(lines[0]) index = 1 test_cases = [] for _ in range(T): N, M = map(int, lines[index].split()) index += 1 edges = [] for _ in range(M): u, v, w = map(int, lines[index].split()) index += 1 edges.append((u, v, w)) test_cases.append((N, M, edges)) results = compute_edge_sums(T, test_cases) return results