D. Contest Balloons

Codeforces

IDCF725D

Time3000ms

Memory256MB

Difficulty—

data structuresgreedy

English · Original

Chinese · Translation

Formal · Original

One tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by the number of balloons they have. It means that one's place is equal to the number of teams with more balloons, increased by 1. For example, if there are seven teams with more balloons, you get the eight place. Ties are allowed. You should know that it's important to eat before a contest. If the number of balloons of a team is greater than the weight of this team, the team starts to float in the air together with their workstation. They eventually touch the ceiling, what is strictly forbidden by the rules. The team is then disqualified and isn't considered in the standings. A contest has just finished. There are _n_ teams, numbered 1 through _n_. The _i_\-th team has _t__i_ balloons and weight _w__i_. It's guaranteed that _t__i_ doesn't exceed _w__i_ so nobody floats initially. Limak is a member of the first team. He doesn't like cheating and he would never steal balloons from other teams. Instead, he can give his balloons away to other teams, possibly making them float. Limak can give away zero or more balloons of his team. Obviously, he can't give away more balloons than his team initially has. What is the best place Limak can get? ## Input The first line of the standard input contains one integer _n_ (2 ≤ _n_ ≤ 300 000) — the number of teams. The _i_\-th of _n_ following lines contains two integers _t__i_ and _w__i_ (0 ≤ _t__i_ ≤ _w__i_ ≤ 1018) — respectively the number of balloons and the weight of the _i_\-th team. Limak is a member of the first team. ## Output Print one integer denoting the best place Limak can get. [samples] ## Note In the first sample, Limak has 20 balloons initially. There are three teams with more balloons (32, 40 and 45 balloons), so Limak has the fourth place initially. One optimal strategy is: 1. Limak gives 6 balloons away to a team with 32 balloons and weight 37, which is just enough to make them fly. Unfortunately, Limak has only 14 balloons now and he would get the fifth place. 2. Limak gives 6 balloons away to a team with 45 balloons. Now they have 51 balloons and weight 50 so they fly and get disqualified. 3. Limak gives 1 balloon to each of two teams with 16 balloons initially. 4. Limak has 20 - 6 - 6 - 1 - 1 = 6 balloons. 5. There are three other teams left and their numbers of balloons are 40, 14 and 2. 6. Limak gets the third place because there are two teams with more balloons. In the second sample, Limak has the second place and he can't improve it. In the third sample, Limak has just enough balloons to get rid of teams 2, 3 and 5 (the teams with 81 000 000 000, 5 000 000 000 and 46 000 000 000 balloons respectively). With zero balloons left, he will get the second place (ex-aequo with team 6 and team 7).

ACM-ICPC 比赛的一个传统是，每解决一个问题，队伍就会获得一个气球。我们假设提交时间无关紧要，队伍仅根据其拥有的气球数量进行排序。这意味着一个队伍的排名等于拥有更多气球的队伍数量加 #cf_span[1]。例如，如果有七个队伍拥有更多气球，你的排名就是第八名。允许并列。你需要知道，在比赛前吃东西是很重要的。如果一个队伍的气球数量大于其体重，该队伍将连同其工作台一起漂浮到空中，最终触碰到天花板，这是规则严格禁止的。这样的队伍将被取消资格，不再计入排名。一场比赛刚刚结束。共有 #cf_span[n] 个队伍，编号从 #cf_span[1] 到 #cf_span[n]。第 #cf_span[i] 个队伍有 #cf_span[ti] 个气球和体重 #cf_span[wi]。保证 #cf_span[ti] 不超过 #cf_span[wi]，因此最初没有人漂浮。 Limak 是第一支队伍的成员。他不喜欢作弊，也绝不会从其他队伍偷气球。相反，他可以把他的气球送给其他队伍，可能会导致他们漂浮。Limak 可以送出零个或多个自己的气球。显然，他不能送出超过自己队伍初始拥有的气球数量。 Limak 能获得的最好排名是多少？标准输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 300 000]) —— 队伍的数量。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ti] 和 #cf_span[wi] (#cf_span[0 ≤ ti ≤ wi ≤ 1018]) —— 分别表示第 #cf_span[i] 个队伍的气球数量和体重。Limak 属于第一支队伍。请输出一个整数，表示 Limak 能获得的最好排名。在第一个样例中，Limak 初始有 #cf_span[20] 个气球。有三个队伍拥有更多气球（#cf_span[32]、#cf_span[40] 和 #cf_span[45]），因此 Limak 初始排名为第四。一种最优策略是：在第二个样例中，Limak 排名第二，且无法再提升。在第三个样例中，Limak 恰好有足够的气球来淘汰第 #cf_span[2]、#cf_span[3] 和 #cf_span[5] 支队伍（分别拥有 #cf_span[81 000 000 000]、#cf_span[5 000 000 000] 和 #cf_span[46 000 000 000] 个气球）。当他剩下零个气球时，他的排名将是第二（与第 #cf_span[6] 和第 #cf_span[7] 队伍并列）。 ## Input 标准输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 300 000]) —— 队伍的数量。第 #cf_span[i] 行包含两个整数 #cf_span[ti] 和 #cf_span[wi] (#cf_span[0 ≤ ti ≤ wi ≤ 1018]) —— 分别表示第 #cf_span[i] 个队伍的气球数量和体重。Limak 属于第一支队伍。 ## Output 请输出一个整数，表示 Limak 能获得的最好排名。 [samples] ## Note 在第一个样例中，Limak 初始有 #cf_span[20] 个气球。有三个队伍拥有更多气球（#cf_span[32]、#cf_span[40] 和 #cf_span[45]），因此 Limak 初始排名为第四。一种最优策略是：Limak 给拥有 #cf_span[32] 个气球、体重为 #cf_span[37] 的队伍送出 #cf_span[6] 个气球，这恰好足以使其漂浮。不幸的是，此时 Limak 只剩下 #cf_span[14] 个气球，排名将变为第五。Limak 给拥有 #cf_span[45] 个气球的队伍送出 #cf_span[6] 个气球。现在该队伍拥有 #cf_span[51] 个气球、体重为 #cf_span[50]，因此漂浮并被取消资格。Limak 给两个初始拥有 #cf_span[16] 个气球的队伍各送出 #cf_span[1] 个气球。Limak 剩下 #cf_span[20 - 6 - 6 - 1 - 1 = 6] 个气球。此时剩下三个队伍，其气球数分别为 #cf_span[40]、#cf_span[14] 和 #cf_span[2]。由于有两个队伍的气球数多于 Limak，他的排名为第三。在第二个样例中，Limak 排名第二，且无法再提升。在第三个样例中，Limak 恰好有足够的气球来淘汰第 #cf_span[2]、#cf_span[3] 和 #cf_span[5] 支队伍（分别拥有 #cf_span[81 000 000 000]、#cf_span[5 000 000 000] 和 #cf_span[46 000 000 000] 个气球）。当他剩下零个气球时，他的排名将是第二（与第 #cf_span[6] 和第 #cf_span[7] 队伍并列）。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of teams. Let $ T_i = (t_i, w_i) $ for $ i \in \{1, \dots, n\} $ be the balloon count and weight of team $ i $, where Limak is team 1. Let $ t_1 $ be Limak’s initial balloon count. **Constraints** 1. $ 2 \leq n \leq 300{,}000 $ 2. $ 0 \leq t_i \leq w_i \leq 10^{18} $ for all $ i \in \{1, \dots, n\} $ 3. $ t_i \leq w_i $ initially (no team floats) 4. Limak may give away any integer number $ x $ of balloons such that $ 0 \leq x \leq t_1 $, reducing his balloon count to $ t_1 - x $. 5. A team $ i \neq 1 $ floats and is disqualified if $ t_i > w_i $ (i.e., if Limak gives it balloons such that its new balloon count exceeds its weight). **Objective** Minimize Limak’s rank, defined as: $$ \text{rank} = 1 + \left| \left\{ j \in \{2, \dots, n\} \setminus D \mid t_j > t_1 - x \right\} \right| $$ where $ D $ is the set of disqualified teams (those with $ t_j + \text{balloons received} > w_j $). Limak may distribute his $ x $ given balloons arbitrarily among other teams (non-negative integer amounts), with the constraint that no team $ j \neq 1 $ receives more than $ w_j - t_j $ balloons (to avoid disqualification). Find the **minimum possible rank** Limak can achieve by optimally choosing $ x \in [0, t_1] $ and distributing the $ x $ balloons to other teams to maximize disqualifications while minimizing the number of remaining teams with strictly more balloons than his new count $ t_1 - x $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

7
14000000003 1000000000000000000
81000000000 88000000000
5000000000 7000000000
15000000000 39000000000
46000000000 51000000000
0 1000000000
0 0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Contest Balloons",
    "description": {
      "content": "One tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by the number of balloons they ha",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF725D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by the number of balloons they ha...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "ACM-ICPC 比赛的一个传统是，每解决一个问题，队伍就会获得一个气球。我们假设提交时间无关紧要，队伍仅根据其拥有的气球数量进行排序。这意味着一个队伍的排名等于拥有更多气球的队伍数量加 #cf_span[1]。例如，如果有七个队伍拥有更多气球，你的排名就是第八名。允许并列。\n\n你需要知道，在比赛前吃东西是很重要的。如果一个队伍的气球数量大于其体重，该队伍将连同其工作台一起漂浮到空中，最终触碰到天...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of teams.  \nLet $ T_i = (t_i, w_i) $ for $ i \\in \\{1, \\dots, n\\} $ be the balloon count and weight of team $ i $, where Limak is team 1.  \nLet ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments