C. Voltage Keepsake

Codeforces

IDCF801C

Time2000ms

Memory256MB

Difficulty—

binary searchmath

English · Original

Chinese · Translation

Formal · Original

You have _n_ devices that you want to use simultaneously. The _i_\-th device uses _a__i_ units of power per second. This usage is continuous. That is, in λ seconds, the device will use λ·_a__i_ units of power. The _i_\-th device currently has _b__i_ units of power stored. All devices can store an arbitrary amount of power. You have a single charger that can plug to any single device. The charger will add _p_ units of power per second to a device. This charging is continuous. That is, if you plug in a device for λ seconds, it will gain λ·_p_ units of power. You can switch which device is charging at any arbitrary unit of time (including real numbers), and the time it takes to switch is negligible. You are wondering, what is the maximum amount of time you can use the devices until one of them hits 0 units of power. If you can use the devices indefinitely, print _\-1_. Otherwise, print the maximum amount of time before any one device hits 0 power. ## Input The first line contains two integers, _n_ and _p_ (1 ≤ _n_ ≤ 100 000, 1 ≤ _p_ ≤ 109) — the number of devices and the power of the charger. This is followed by _n_ lines which contain two integers each. Line _i_ contains the integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ 100 000) — the power of the device and the amount of power stored in the device in the beginning. ## Output If you can use the devices indefinitely, print _\-1_. Otherwise, print the maximum amount of time before any one device hits 0 power. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4. Namely, let's assume that your answer is _a_ and the answer of the jury is _b_. The checker program will consider your answer correct if . [samples] ## Note In sample test 1, you can charge the first device for the entire time until it hits zero power. The second device has enough power to last this time without being charged. In sample test 2, you can use the device indefinitely. In sample test 3, we can charge the third device for 2 / 5 of a second, then switch to charge the second device for a 1 / 10 of a second.

你有 #cf_span[n] 个设备，希望同时使用它们。第 #cf_span[i] 个设备每秒消耗 #cf_span[ai] 单位的电量。这种消耗是连续的。也就是说，在 #cf_span[λ] 秒内，该设备将消耗 #cf_span[λ·ai] 单位的电量。第 #cf_span[i] 个设备当前存储了 #cf_span[bi] 单位的电量。所有设备都可以存储任意数量的电量。你有一个充电器，可以连接到任意一个设备上。该充电器每秒向设备提供 #cf_span[p] 单位的电量。这种充电是连续的。也就是说，如果你将一个设备充电 #cf_span[λ] 秒，它将获得 #cf_span[λ·p] 单位的电量。你可以在任意时刻（包括实数时间）切换充电的设备，且切换所需时间可忽略不计。你需要确定：在任一设备电量降至 #cf_span[0] 之前，你能持续使用这些设备的最长时间是多少？如果可以无限期使用这些设备，请输出 _-1_。否则，请输出任一设备电量降至 #cf_span[0] 之前的最长时间。第一行包含两个整数 #cf_span[n] 和 #cf_span[p]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ p ≤ 10^9]）—— 设备数量和充电器功率。接下来有 #cf_span[n] 行，每行包含两个整数。第 #cf_span[i] 行包含整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 100 000]）—— 设备的功率消耗和初始存储电量。如果可以无限期使用这些设备，请输出 _-1_。否则，请输出任一设备电量降至 #cf_span[0] 之前的最长时间。你的答案若绝对误差或相对误差不超过 #cf_span[10^{-4}]，则被视为正确。具体来说，假设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，判题程序将认为你的答案正确当且仅当。在样例测试 1 中，你可以在整个过程中持续为第一个设备充电，直到其电量耗尽。第二个设备的电量足以在不充电的情况下维持这段时间。在样例测试 2 中，你可以无限期使用该设备。在样例测试 3 中，我们可以先为第三个设备充电 #cf_span[2 / 5] 秒，然后切换为对第二个设备充电 #cf_span[1 / 10] 秒。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[p]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ p ≤ 10^9]）—— 设备数量和充电器功率。接下来有 #cf_span[n] 行，每行包含两个整数。第 #cf_span[i] 行包含整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 100 000]）—— 设备的功率消耗和初始存储电量。 ## Output 如果可以无限期使用这些设备，请输出 _-1_。否则，请输出任一设备电量降至 #cf_span[0] 之前的最长时间。你的答案若绝对误差或相对误差不超过 #cf_span[10^{-4}]，则被视为正确。具体来说，假设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，判题程序将认为你的答案正确当且仅当。 [samples] ## Note 在样例测试 1 中，你可以在整个过程中持续为第一个设备充电，直到其电量耗尽。第二个设备的电量足以在不充电的情况下维持这段时间。在样例测试 2 中，你可以无限期使用该设备。在样例测试 3 中，我们可以先为第三个设备充电 #cf_span[2 / 5] 秒，然后切换为对第二个设备充电 #cf_span[1 / 10] 秒。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of devices, and $ p \in \mathbb{R}^+ $ be the charging rate (units per second). For each device $ i \in \{1, \dots, n\} $: - Let $ a_i \in \mathbb{R}^+ $ be the power consumption rate (units per second). - Let $ b_i \in \mathbb{R}^+ $ be the initial power储备. Let $ t \in \mathbb{R}^+ \cup \{\infty\} $ be the maximum time until any device reaches 0 power. Let $ x_i(t) \in [0, t] $ be the total time during $ [0, t] $ that device $ i $ is being charged. **Constraints** 1. $ \sum_{i=1}^n x_i(t) \le t $ (charger can serve only one device at a time). 2. For each device $ i $, the power at time $ t $ must be non-negative: $$ b_i - a_i t + p x_i(t) \ge 0 $$ 3. $ x_i(t) \ge 0 $ for all $ i $. **Objective** Find the maximum $ t $ such that there exist $ x_1(t), \dots, x_n(t) \in [0, t] $ satisfying the above constraints. If such $ t $ can be arbitrarily large, output $ -1 $. **Note**: The problem reduces to checking whether $ \sum_{i=1}^n a_i \le p $ (then $ t = \infty $), else solving for the maximum $ t $ such that: $$ \sum_{i=1}^n \max\left(0, \frac{a_i t - b_i}{p}\right) \le t $$

Samples

Input #1

2 1
2 2
2 1000

Output #1

2.0000000000

Input #2

1 100
1 1

Output #2

\-1

Input #3

Output #3

0.5000000000

API Response (JSON)

{
  "problem": {
    "name": "C. Voltage Keepsake",
    "description": {
      "content": "You have _n_ devices that you want to use simultaneously. The _i_\\-th device uses _a__i_ units of power per second. This usage is continuous. That is, in λ seconds, the device will use λ·_a__i_ units",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF801C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have _n_ devices that you want to use simultaneously.\n\nThe _i_\\-th device uses _a__i_ units of power per second. This usage is continuous. That is, in λ seconds, the device will use λ·_a__i_ units...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你有 #cf_span[n] 个设备，希望同时使用它们。\n\n第 #cf_span[i] 个设备每秒消耗 #cf_span[ai] 单位的电量。这种消耗是连续的。也就是说，在 #cf_span[λ] 秒内，该设备将消耗 #cf_span[λ·ai] 单位的电量。第 #cf_span[i] 个设备当前存储了 #cf_span[bi] 单位的电量。所有设备都可以存储任意数量的电量。\n\n你有一个充电器，可...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of devices, and $ p \\in \\mathbb{R}^+ $ be the charging rate (units per second).  \nFor each device $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ a_i \\i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments