F. Compute Power

你需要执行若干任务，每个任务需要一定数量的处理器，并消耗一定的计算功率。 你拥有足够多的模拟计算机，每台计算机的处理器数量足以胜任任何任务。每台计算机一次最多执行一个任务，总共最多执行两个任务。每台计算机的第一个任务可以是任意的，但第二个任务的功率必须严格小于第一个任务。你将为每台计算机分配 1 到 2 个任务，然后先在所有计算机上同时执行第一个任务，等待全部完成，再在那些分配了两个任务的计算机上执行第二个任务。 如果在执行第一轮任务期间，所有计算机中“每台被利用的处理器的平均计算功率”（即当前所有运行任务的功率总和除以被利用的处理器总数）超过某个未知阈值，整个系统将爆炸。对第二轮任务的执行没有限制。请找出能使系统不爆炸的最低阈值。 由于任务的特殊性，你需要输出该阈值乘以 1000 并向上取整后的结果。 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 50]) —— 任务的数量。 第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 108])，其中 #cf_span[ai] 表示第 #cf_span[i] 个任务所需的功率。 第三行包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn] (#cf_span[1 ≤ bi ≤ 100])，其中 #cf_span[bi] 表示第 #cf_span[i] 个任务将利用的处理器数量。 请输出一个整数 —— 能够成功分配所有任务、使系统在第一轮计算后不爆炸的最低阈值，乘以 1000 并向上取整后的值。 在第一个示例中，最佳策略是将每个任务单独分配到一台计算机上，此时第一轮的每处理器平均功率为 9。 在第二个示例中，最佳策略是：一台计算机执行功率为 10 和 9 的任务，另一台执行功率为 10 和 8 的任务，最后一台执行功率为 9 和 8 的任务，第一轮的平均功率为 (10 + 10 + 9) / (10 + 10 + 5) = 1.16 每处理器。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 50]) —— 任务的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 108])，其中 #cf_span[ai] 表示第 #cf_span[i] 个任务所需的功率。第三行包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn] (#cf_span[1 ≤ bi ≤ 100])，其中 #cf_span[bi] 表示第 #cf_span[i] 个任务将利用的处理器数量。 ## Output 请输出一个整数 —— 能够成功分配所有任务、使系统在第一轮计算后不爆炸的最低阈值，乘以 1000 并向上取整后的值。 [samples] ## Note 在第一个示例中，最佳策略是将每个任务单独分配到一台计算机上，此时第一轮的每处理器平均功率为 9。在第二个示例中，最佳策略是：一台计算机执行功率为 10 和 9 的任务，另一台执行功率为 10 和 8 的任务，最后一台执行功率为 9 和 8 的任务，第一轮的平均功率为 (10 + 10 + 9) / (10 + 10 + 5) = 1.16 每处理器。

Let $ n $ be the number of tasks. For each task $ i \in \{1, 2, \dots, n\} $, let: - $ a_i $: compute power required, - $ b_i $: number of processors utilized. Each computer can execute **at most two tasks**: - First task (primary) with power $ a_p $, processors $ b_p $, - Second task (secondary) with power $ a_s $, processors $ b_s $, such that $ a_s < a_p $. Each task is assigned to **exactly one** computer. Each computer gets **1 or 2** tasks. All **first tasks** are executed simultaneously in round 1. The **average compute power per utilized processor** during round 1 is: $$ \frac{\sum_{\text{first tasks } i} a_i}{\sum_{\text{first tasks } i} b_i} $$ We must assign tasks to computers (with the constraint that if a computer has two tasks, the second must have strictly less power than the first) such that this average is **minimized**, and we must find the **minimum possible value** of this average over all valid assignments. Then, output $ \lceil 1000 \times \text{minimum average} \rceil $. --- **Formal Statement:** Let $ T = \{1, 2, \dots, n\} $ be the set of tasks. Each task $ i \in T $ has power $ a_i $ and processor count $ b_i $. Define a partition of $ T $ into disjoint subsets $ C_1, C_2, \dots, C_k $, where each $ C_j $ is a computer assignment: - $ |C_j| \in \{1, 2\} $, - If $ |C_j| = 2 $, let $ p_j $ be the task in $ C_j $ with **maximum** power, and $ s_j $ the one with **minimum** power. Then $ a_{s_j} < a_{p_j} $ must hold. Let $ F \subseteq T $ be the set of **first tasks** (i.e., the task with higher power in each pair, or the only task in a singleton). Define: $$ A = \sum_{i \in F} a_i, \quad B = \sum_{i \in F} b_i $$ We seek to **minimize** $ \frac{A}{B} $ over all valid assignments. Then output $ \left\lceil 1000 \cdot \min \frac{A}{B} \right\rceil $. --- **Constraints:** - $ 1 \leq n \leq 50 $ - $ 1 \leq a_i \leq 10^8 $ - $ 1 \leq b_i \leq 100 $ Note: Since $ n \leq 50 $, we can use dynamic programming or greedy matching with sorting, but the core formal problem is: > Minimize $ \frac{\sum a_i \text{ over first tasks}}{\sum b_i \text{ over first tasks}} $, under the constraint that second tasks (if any) have strictly smaller power than their paired first task, and each task is used exactly once. This is equivalent to: **Select a subset $ F \subseteq T $** to be the first tasks, such that the remaining tasks $ T \setminus F $ can be **paired** with tasks in $ F $ satisfying $ a_s < a_p $, and each task in $ F $ can be paired with at most one task from $ T \setminus F $. Minimize $ \frac{\sum_{i \in F} a_i}{\sum_{i \in F} b_i} $. This is a **fractional programming** problem with matching constraints. However, due to small $ n \leq 50 $, we can consider: - Sort tasks by power descending. - Use DP over subsets or greedy pairing: for each possible subset $ F $ of tasks (as first tasks), check if the complement can be matched to $ F $ with $ a_s < a_p $, and compute the ratio. But the **minimal possible ratio** is achieved by a **greedy matching** after sorting. Standard solution approach (known from similar problems): 1. Sort tasks by $ a_i $ descending. 2. Use DP: $ dp[i][j] $ = minimal total power / total processors for first tasks among first $ i $ tasks, having used $ j $ tasks as first tasks, and having matched some second tasks. But since ratio is fractional, better to use binary search on the ratio. Alternatively, since $ n \leq 50 $, and the number of first tasks can be from $ \lceil n/2 \rceil $ to $ n $, we can iterate over all possible subsets $ F $ of size $ \lceil n/2 \rceil $ to $ n $, and for each, check if the remaining tasks can be assigned as second tasks with $ a_s < a_p $, and compute $ A/B $, then take minimum. But even better: use **greedy matching after sorting**. **Optimal strategy:** - Sort tasks in **descending order of $ a_i $**. - Use two pointers or DP to pair each potential first task with a lower-power task if possible. - The minimal average occurs when we **maximize the number of second tasks** (since we can "hide" high-power tasks as second tasks — but we cannot, because second tasks must be strictly less than first, so high-power tasks must be first tasks). Actually: **High-power tasks must be first tasks**, because no task has higher power to be paired with them as second. So: **The highest-power task must be a first task.** Then: We can try to pair as many low-power tasks as possible with high-power first tasks to reduce the number of first tasks → which reduces numerator and denominator, but we need to minimize the ratio. This becomes a **minimum ratio covering with matching constraints**. Known solution in competitive programming: Sort tasks by $ a_i $ descending. Let $ dp[i] $ be the minimal total power and total processors for first tasks among the first $ i $ tasks, with the constraint that the remaining tasks (from $ i+1 $ to $ n $) can be matched as second tasks. But better: use **binary search on the ratio $ r $**. We want to know: Is there an assignment such that $$ \frac{\sum_{i \in F} a_i}{\sum_{i \in F} b_i} \leq r \quad \iff \quad \sum_{i \in F} (a_i - r \cdot b_i) \leq 0 $$ So we can binary search on $ r $, and for a fixed $ r $, check if there exists a valid assignment where the sum $ \sum_{i \in F} (a_i - r b_i) \leq 0 $, and the complement can be matched to $ F $ with $ a_s < a_p $. To check feasibility for fixed $ r $: - Sort tasks by $ a_i $ descending. - Use DP: state $ dp[i][j] $ = minimum value of $ \sum (a_k - r b_k) $ for first tasks among first $ i $ tasks, with $ j $ tasks used as second tasks (i.e., matched to some first task among the first $ i $). - Transition: for task $ i $, we can either: - Make it a first task: add $ a_i - r b_i $, and increment first-task count. - Make it a second task: only possible if there exists a first task among the previous tasks with higher power (which is guaranteed since sorted descending), and we haven’t used it up — so we need to track how many unmatched first tasks we have. Actually, standard solution: After sorting by $ a_i $ descending, we can use DP where: - $ dp[i][j] $ = minimum value of $ \sum_{k \in F} (a_k - r b_k) $ after processing first $ i $ tasks, with $ j $ unmatched first tasks (i.e., first tasks that haven’t been paired with a second task yet). Then for task $ i $: - Option 1: Use as first task → $ dp[i][j+1] = \min(dp[i][j+1], dp[i-1][j] + a_i - r b_i) $ - Option 2: Use as second task → must pair with one of the previous unmatched first tasks → $ dp[i][j-1] = \min(dp[i][j-1], dp[i-1][j]) $, only if $ j > 0 $ Base: $ dp[0][0] = 0 $ At the end, we require $ dp[n][0] \leq 0 $, meaning all tasks are assigned, and no unmatched first tasks (all first tasks are either used alone or paired). Wait: We can have unmatched first tasks (singleton computers). So we don’t require $ j=0 $, we require that all tasks are assigned, and second tasks are only assigned to first tasks with higher $ a $, which is satisfied by descending sort. Actually, we allow $ j \geq 0 $ at the end — as long as we’ve assigned all tasks. So: after processing all $ n $ tasks, we can have any $ j \geq 0 $, as long as $ dp[n][j] \leq 0 $ for some $ j $. But we must have used all tasks. The DP above ensures that: each task is either first or second. So for fixed $ r $, we can compute $ \min_j dp[n][j] $, and if $ \min_j dp[n][j] \leq 0 $, then $ r $ is achievable. Then binary search on $ r $ from 0 to $ \max a_i $. Then output $ \lceil 1000 \cdot r_{\min} \rceil $. This is the standard solution for "minimum ratio matching with pairing constraint". --- **Final Formal Statement:** Let $ T = \{1, \dots, n\} $, with tasks $ (a_i, b_i) $. Sort tasks in descending order of $ a_i $. Define function $ f(r) $: $ f(r) = \min \left\{ \sum_{i \in F} (a_i - r b_i) \mid F \subseteq T, \text{ and } T \setminus F \text{ can be matched to } F \text{ with } a_s < a_p \right\} $ We seek the minimal $ r $ such that $ f(r) \leq 0 $. Compute $ r^* = \min \{ r \in \mathbb{R} \mid f(r) \leq 0 \} $ Then output $ \left\lceil 1000 \cdot r^* \right\rceil $ This is solvable via binary search on $ r $ with dynamic programming as described. --- **Answer (formal mathematical statement):** Let $ (a_i, b_i)_{i=1}^n $ be given, with $ a_i \in \mathbb{R}^+, b_i \in \mathbb{N}^+ $. Sort $ (a_i, b_i) $ in descending order of $ a_i $. Define DP state $ dp[i][j] $ as the minimum value of $ \sum_{k=1}^i (a_k - r b_k) \cdot \mathbf{1}_{\text{task } k \in F} $ over all valid assignments of the first $ i $ tasks, where $ j $ is the number of unmatched first tasks (i.e., first tasks not yet paired with a second task). Transitions: - $ dp[0][0] = 0 $, $ dp[0][j] = \infty $ for $ j > 0 $ - For $ i \geq 1 $: - $ dp[i][j] = \min \left( dp[i-1][j-1] + a_i - r b_i, \quad dp[i-1][j+1] \right) $ (first option: make task $ i $ a first task → unmatched count increases by 1; second option: make task $ i $ a second task → must pair with one unmatched first task → unmatched count decreases by 1) Then $ f(r) = \min_{j \geq 0} dp[n][j] $ Find the minimal $ r $ such that $ f(r) \leq 0 $ Output $ \left\lceil 1000 \cdot r \right\rceil $ --- This is the complete formal mathematical statement.