B. News About Credit

Codeforces

IDCF769B

Time1000ms

Memory256MB

Difficulty—

greedytwo pointers

English · Original

Chinese · Translation

Formal · Original

Polycarp studies at the university in the group which consists of _n_ students (including himself). All they are registrated in the social net "TheContacnt!". Not all students are equally sociable. About each student you know the value _a__i_ — the maximum number of messages which the _i_\-th student is agree to send per day. The student can't send messages to himself. In early morning Polycarp knew important news that the programming credit will be tomorrow. For this reason it is necessary to urgently inform all groupmates about this news using private messages. Your task is to make a plan of using private messages, so that: * the student _i_ sends no more than _a__i_ messages (for all _i_ from 1 to _n_); * all students knew the news about the credit (initially only Polycarp knew it); * the student can inform the other student only if he knows it himself. Let's consider that all students are numerated by distinct numbers from 1 to _n_, and Polycarp **always** has the number 1. In that task you shouldn't minimize the number of messages, the moment of time, when all knew about credit or some other parameters. Find any way how to use private messages which satisfies requirements above. ## Input The first line contains the positive integer _n_ (2 ≤ _n_ ≤ 100) — the number of students. The second line contains the sequence _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 100), where _a__i_ equals to the maximum number of messages which can the _i_\-th student agree to send. Consider that Polycarp **always** has the number 1. ## Output Print _\-1_ to the first line if it is impossible to inform all students about credit. Otherwise, in the first line print the integer _k_ — the number of messages which will be sent. In each of the next _k_ lines print two **distinct** integers _f_ and _t_, meaning that the student number _f_ sent the message with news to the student number _t_. All messages should be printed in chronological order. It means that the student, who is sending the message, must already know this news. It is assumed that students can receive repeated messages with news of the credit. If there are several answers, it is acceptable to print any of them. [samples] ## Note In the first test Polycarp (the student number 1) can send the message to the student number 2, who after that can send the message to students number 3 and 4. Thus, all students knew about the credit.

Polycarp 在大学的一个由 #cf_span[n] 名学生（包括他自己）组成的小组学习。他们都注册了社交网络 "TheContacnt!"。并非所有学生都同样外向。对于每个学生，你知道一个值 #cf_span[ai] —— 第 #cf_span[i] 名学生每天愿意发送的最大消息数。学生不能给自己发消息。清晨，Polycarp 得知一个重要消息：编程考试将在明天举行。因此，必须通过私信紧急通知所有组员这一消息。你的任务是制定一个私信使用计划，使得：假设所有学生用从 #cf_span[1] 到 #cf_span[n] 的不同数字编号，且 Polycarp *始终* 编号为 #cf_span[1]。在此任务中，你无需最小化消息数量、所有学生得知消息的时间或其他参数。只需找到一种满足上述要求的私信使用方式即可。第一行包含一个正整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 学生人数。第二行包含序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 100])，其中 #cf_span[ai] 表示第 #cf_span[i] 名学生愿意发送的最大消息数。注意 Polycarp *始终* 编号为 #cf_span[1]。如果无法通知所有学生关于考试的消息，请在第一行输出 _-1_。否则，在第一行输出整数 #cf_span[k] —— 将要发送的消息总数。接下来的 #cf_span[k] 行中，每行输出两个 *互不相同* 的整数 #cf_span[f] 和 #cf_span[t]，表示编号为 #cf_span[f] 的学生向编号为 #cf_span[t] 的学生发送了包含消息的私信。所有消息应按时间顺序输出，即发送消息的学生必须已经知晓该消息。假定学生可以多次收到关于考试的消息。如果有多个答案，输出任意一个均可。在第一个测试中，Polycarp（学生编号 #cf_span[1]）可以向学生编号 #cf_span[2] 发送消息，之后该学生可以向学生编号 #cf_span[3] 和 #cf_span[4] 发送消息。因此，所有学生都得知了考试消息。 ## Input 第一行包含一个正整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 学生人数。第二行包含序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 100])，其中 #cf_span[ai] 表示第 #cf_span[i] 名学生愿意发送的最大消息数。注意 Polycarp *始终* 编号为 #cf_span[1]。 ## Output 如果无法通知所有学生关于考试的消息，请在第一行输出 _-1_。否则，在第一行输出整数 #cf_span[k] —— 将要发送的消息总数。接下来的 #cf_span[k] 行中，每行输出两个 *互不相同* 的整数 #cf_span[f] 和 #cf_span[t]，表示编号为 #cf_span[f] 的学生向编号为 #cf_span[t] 的学生发送了包含消息的私信。所有消息应按时间顺序输出，即发送消息的学生必须已经知晓该消息。假定学生可以多次收到关于考试的消息。如果有多个答案，输出任意一个均可。 [samples] ## Note 在第一个测试中，Polycarp（学生编号 #cf_span[1]）可以向学生编号 #cf_span[2] 发送消息，之后该学生可以向学生编号 #cf_span[3] 和 #cf_span[4] 发送消息。因此，所有学生都得知了考试消息。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of students, with $ 2 \leq n \leq 100 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the maximum number of messages student $ i $ can send. Student 1 (Polycarp) initially knows the news. **Constraints** 1. $ 0 \leq a_i \leq 100 $ for all $ i \in \{1, \dots, n\} $ 2. Students cannot send messages to themselves. 3. A message from student $ f $ to student $ t $ is valid only if $ f $ already knows the news. 4. The goal is to inform all students $ \{1, 2, \dots, n\} $. **Objective** Determine if there exists a sequence of messages such that: - All students eventually know the news. - Each student $ i $ sends at most $ a_i $ messages. - Messages are sent in chronological order (sender must know the news before sending). If possible: - Output the number of messages $ k $, followed by $ k $ ordered pairs $ (f, t) $ representing messages. - If impossible: output $-1$.

Samples

Input #1

4
1 2 1 0

Output #1

Input #2

6
2 0 1 3 2 0

Output #2

Input #3

3
0 2 2

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. News About Credit",
    "description": {
      "content": "Polycarp studies at the university in the group which consists of _n_ students (including himself). All they are registrated in the social net \"TheContacnt!\". Not all students are equally sociable. A",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF769B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp studies at the university in the group which consists of _n_ students (including himself). All they are registrated in the social net \"TheContacnt!\".\n\nNot all students are equally sociable. A...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 在大学的一个由 #cf_span[n] 名学生（包括他自己）组成的小组学习。他们都注册了社交网络 \"TheContacnt!\"。\n\n并非所有学生都同样外向。对于每个学生，你知道一个值 #cf_span[ai] —— 第 #cf_span[i] 名学生每天愿意发送的最大消息数。学生不能给自己发消息。\n\n清晨，Polycarp 得知一个重要消息：编程考试将在明天举行。因此，必须通过私...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of students, with $ 2 \\leq n \\leq 100 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the maxi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments