C. New Year and Rating

Codeforces

IDCF750C

Time2000ms

Memory256MB

Difficulty—

binary searchgreedymath

English · Original

Chinese · Translation

Formal · Original

Every Codeforces user has rating, described with one integer, possibly negative or zero. Users are divided into two divisions. The first division is for users with rating 1900 or higher. Those with rating 1899 or lower belong to the second division. In every contest, according to one's performance, his or her rating changes by some value, possibly negative or zero. Limak competed in _n_ contests in the year 2016. He remembers that in the _i_\-th contest he competed in the division _d__i_ (i.e. he belonged to this division **just before** the start of this contest) and his rating changed by _c__i_ **just after the contest**. Note that negative _c__i_ denotes the loss of rating. What is the maximum possible rating Limak can have right now, after all _n_ contests? If his rating may be arbitrarily big, print "_Infinity_". If there is no scenario matching the given information, print "_Impossible_". ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 200 000). The _i_\-th of next _n_ lines contains two integers _c__i_ and _d__i_ ( - 100 ≤ _c__i_ ≤ 100, 1 ≤ _d__i_ ≤ 2), describing Limak's rating change after the _i_\-th contest and his division during the _i_\-th contest contest. ## Output If Limak's current rating can be arbitrarily big, print "_Infinity_" (without quotes). If the situation is impossible, print "_Impossible_" (without quotes). Otherwise print one integer, denoting the maximum possible value of Limak's current rating, i.e. rating after the _n_ contests. [samples] ## Note In the first sample, the following scenario matches all information Limak remembers and has maximum possible final rating: * Limak has rating 1901 and belongs to the division 1 in the first contest. His rating decreases by 7. * With rating 1894 Limak is in the division 2. His rating increases by 5. * Limak has rating 1899 and is still in the division 2. In the last contest of the year he gets + 8 and ends the year with rating 1907. In the second sample, it's impossible that Limak is in the division 1, his rating increases by 57 and after that Limak is in the division 2 in the second contest.

每个 Codeforces 用户都有一个评分，用一个整数表示，可能为负数或零。用户被分为两个组。第一组是评分不低于 #cf_span[1900] 的用户，评分不高于 #cf_span[1899] 的用户属于第二组。在每场比赛中，根据选手的表现，其评分会变化某个值，可能为负数或零。 Limak 在 2016 年参加了 #cf_span[n] 场比赛。他记得，在第 #cf_span[i] 场比赛中，他在比赛开始前属于第 #cf_span[di] 组（即比赛开始前他属于该组），比赛结束后他的评分变化了 #cf_span[ci]（注意，负的 #cf_span[ci] 表示评分下降）。在所有 #cf_span[n] 场比赛结束后，Limak 当前评分的最大可能值是多少？如果他的评分可以任意大，请输出 "_Infinity_"。如果不存在符合给定信息的任何情况，请输出 "_Impossible_"。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ci] 和 #cf_span[di]（#cf_span[ - 100 ≤ ci ≤ 100]，#cf_span[1 ≤ di ≤ 2]），分别描述 Limak 在第 #cf_span[i] 场比赛后的评分变化以及他在第 #cf_span[i] 场比赛期间所属的组别。如果 Limak 的当前评分可以任意大，请输出 "_Infinity_"（不含引号）。如果情况不可能，请输出 "_Impossible_"（不含引号）。否则，请输出一个整数，表示 Limak 当前评分（即第 #cf_span[n] 场比赛后的评分）的最大可能值。在第一个样例中，以下场景符合 Limak 记忆中的所有信息，并且具有最大的最终评分：在第二个样例中，Limak 不可能在第一场比赛时属于第 #cf_span[1] 组，评分增加 #cf_span[57]，然后在第二场比赛时属于第 #cf_span[2] 组。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ci] 和 #cf_span[di]（#cf_span[ - 100 ≤ ci ≤ 100]，#cf_span[1 ≤ di ≤ 2]），分别描述 Limak 在第 #cf_span[i] 场比赛后的评分变化以及他在第 #cf_span[i] 场比赛期间所属的组别。 ## Output 如果 Limak 的当前评分可以任意大，请输出 "_Infinity_"（不含引号）。如果情况不可能，请输出 "_Impossible_"（不含引号）。否则，请输出一个整数，表示 Limak 当前评分（即第 #cf_span[n] 场比赛后的评分）的最大可能值。 [samples] ## Note 在第一个样例中，以下场景符合 Limak 记忆中的所有信息，并且具有最大的最终评分：Limak 在第一场比赛前评分为 #cf_span[1901]，属于第 #cf_span[1] 组。他的评分下降 #cf_span[7]。此时评分为 #cf_span[1894]，属于第 #cf_span[2] 组。他的评分增加 #cf_span[5]。此时评分为 #cf_span[1899]，仍属于第 #cf_span[2] 组。在年度最后一场比赛中，他获得 #cf_span[ + 8]，最终评分为 #cf_span[1907]。在第二个样例中，Limak 不可能在第一场比赛时属于第 #cf_span[1] 组，评分增加 #cf_span[57]，然后在第二场比赛时属于第 #cf_span[2] 组。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of contests. For $ i \in \{1, \dots, n\} $: - Let $ c_i \in \mathbb{Z} $ denote the rating change after contest $ i $, with $ -100 \leq c_i \leq 100 $. - Let $ d_i \in \{1, 2\} $ denote the division Limak belonged to *just before* contest $ i $. Let $ r_0 \in \mathbb{Z} $ be Limak’s initial rating (before contest 1). Let $ r_i = r_0 + \sum_{j=1}^i c_j $ be Limak’s rating *after* contest $ i $, for $ i \in \{1, \dots, n\} $. **Constraints** For each $ i \in \{1, \dots, n\} $: - If $ d_i = 1 $, then $ r_{i-1} \geq 1900 $. - If $ d_i = 2 $, then $ r_{i-1} \leq 1899 $. **Objective** Maximize $ r_n = r_0 + \sum_{i=1}^n c_i $, subject to the above constraints. If no such $ r_0 $ exists, output "Impossible". If $ r_0 $ can be made arbitrarily large while satisfying constraints, output "Infinity".

Samples

Input #1

Output #1

Input #2

2
57 1
22 2

Output #2

Impossible

Input #3

1
-5 1

Output #3

Infinity

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "C. New Year and Rating",
    "description": {
      "content": "Every Codeforces user has rating, described with one integer, possibly negative or zero. Users are divided into two divisions. The first division is for users with rating 1900 or higher. Those with ra",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF750C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Every Codeforces user has rating, described with one integer, possibly negative or zero. Users are divided into two divisions. The first division is for users with rating 1900 or higher. Those with ra...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "每个 Codeforces 用户都有一个评分，用一个整数表示，可能为负数或零。用户被分为两个组。第一组是评分不低于 #cf_span[1900] 的用户，评分不高于 #cf_span[1899] 的用户属于第二组。在每场比赛中，根据选手的表现，其评分会变化某个值，可能为负数或零。\n\nLimak 在 2016 年参加了 #cf_span[n] 场比赛。他记得，在第 #cf_span[i] 场比赛中，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of contests.  \nFor $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ c_i \\in \\mathbb{Z} $ denote the rating change after contest $ i $, with $ -100 \\leq c...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments