E. Election of a Mayor

Codeforces

IDCF10051E

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

The Berland capital is preparing for mayoral election. There are two candidates for the position: the current mayor and his rival. The rival is a serious competitor, and it's not easy for current mayor to win the election. The candidate will be declared the winner if he wins at _more_ than a half of _all_ polling stations. The results of the polling stations are supplied independently. The station winner is the candidate who gets _more_ than a half of the votes of this station. No candidate is declared a winner of a polling station if both candidates have got the same number of votes at this station. Similarly, no candidate is declared a winner of the election if both candidates won at the same number of polling stations. All eligible voters are going to take part in the election and have already decided whom to give their vote to. The campaign headquarters of the current mayor has collected data from all n stations of the city, and now for every station it is known how many people will vote for the current mayor and how many people will vote for his opponent. The results have been disappointing for the current mayor, but his staff came up with a way to win the election. It was suggested to merge some pairs of polling stations in such a way that the current mayor will become the election winner. However, (for the sake of credibility), the proposed plan must comply with two conditions. Firstly, it is possible to merge only the pairs of stations with adjacent numbers (i.e., station j may be merged with either station j - 1, or with station j + 1). The resulting station cannot be merged again. Secondly, the number of such mergers for obvious reasons must be as few as possible. Your task is to help the current mayor's campaign headquarters and produce such plan. The first line contains single integer n (2 ≤ n ≤ 2·105) — the number of the polling stations. Each of the following n lines contains two integers mj and rj (0 ≤ mj, rj ≤ 105) — the number of voters at station j who plan to vote for the current mayor and his rival correspondingly. If current mayor cannot win the election at any condition, print a single number - 1 to the first line. Otherwise, to the first line print an integer u — the minimum number of polling station mergers the current mayor needs to perform in order to win. To each of the next u lines print a pair of integers — the numbers of the merged stations. The pairs as well as the numbers within each pair can be printed in any order. If there are multiple solutions, print any of them. ## Input The first line contains single integer n (2 ≤ n ≤ 2·105) — the number of the polling stations. Each of the following n lines contains two integers mj and rj (0 ≤ mj, rj ≤ 105) — the number of voters at station j who plan to vote for the current mayor and his rival correspondingly. ## Output If current mayor cannot win the election at any condition, print a single number - 1 to the first line.Otherwise, to the first line print an integer u — the minimum number of polling station mergers the current mayor needs to perform in order to win. To each of the next u lines print a pair of integers — the numbers of the merged stations. The pairs as well as the numbers within each pair can be printed in any order. If there are multiple solutions, print any of them. [samples]

**Definitions** Let $ s \in \{ \text{U}, \text{F}, \text{ } \}^* $ be the encrypted string, with $ 1 \leq |s| \leq 10^5 $. **Constraints** Each character of $ s $ is in $ \{ \text{U}, \text{F}, \text{ } \} $. **Objective** Decrypt $ s $ to recover the original string. *(Note: The decryption algorithm is unspecified; formalization requires the mapping. Without it, the objective cannot be mathematically defined.)*

API Response (JSON)

{
  "problem": {
    "name": "E. Election of a Mayor",
    "description": {
      "content": "The Berland capital is preparing for mayoral election. There are two candidates for the position: the current mayor and his rival. The rival is a serious competitor, and it's not easy for current mayo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10051E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Berland capital is preparing for mayoral election. There are two candidates for the position: the current mayor and his rival. The rival is a serious competitor, and it's not easy for current mayo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{ \\text{U}, \\text{F}, \\text{ } \\}^* $ be the encrypted string, with $ 1 \\leq |s| \\leq 10^5 $.\n\n**Constraints**  \nEach character of $ s $ is in $ \\{ \\text{U}, \\text{F}, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments