CF769B.News About Credit

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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.

波利卡普所在的大学班级共有 nn 名学生(包括他自己)。所有学生均注册了社交网络“TheContacnt!”。

并非所有学生都同样善于交际。对于每位学生 ii,已知其每日最多愿意发送的消息数 aia_i。每位学生不能给自己发送消息。

清晨,波利卡普得知一条重要消息:编程课程的期末考试将于明天举行。因此,必须立即通过私信将该消息通知班上所有同学。

你的任务是制定一个私信发送方案,使得:

  • 学生 ii 发送的消息数不超过 aia_i(对所有 ii 从 11 到 nn 均成立);
  • 所有学生均获知期末考试的消息(初始时仅波利卡普知道该消息);
  • 一名学生仅当自己已知该消息时,才能将消息告知其他学生。

假设所有学生被编号为互不相同的整数 11 至 nn,且波利卡普的编号恒为 11。

本题不要求最小化消息总数、所有学生获知消息的时间点或其他任何参数。请找出任意一种满足上述要求的私信发送方案。

输入格式

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.

第一行包含一个正整数 nn(2≤n≤1002 \leq n \leq 100)—— 学生人数。

第二行包含序列 a1,a2,…,ana_1, a_2, \dots, a_n(0≤ai≤1000 \leq a_i \leq 100),其中 aia_i 表示第 ii 位学生同意发送的最大消息数量。注意:Polycarp 的编号始终为 11。

输出格式

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.

如果无法通知所有学生关于学分的消息,则在第一行输出 -1。

否则,在第一行输出整数 k —— 即将发送的消息数量。接下来的 k 行中,每行输出两个不同的整数 f 和 t,表示编号为 f 的学生向编号为 t 的学生发送了关于学分的消息。所有消息必须按时间顺序输出,即发送消息的学生必须已经知晓该消息。假定学生可以重复接收关于学分的消息。

若存在多个可行解,输出任意一个即可。

输入输出样例

  • 输入#1

    4
    1 2 1 0

    输出#1

    3
    1 2
    2 4
    2 3
  • 输入#2

    6
    2 0 1 3 2 0

    输出#2

    6
    1 3
    3 4
    1 2
    4 5
    5 6
    4 6
  • 输入#3

    3
    0 2 2

    输出#3

    -1

说明/提示

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.

在第一次测试中,波利卡普(学号为 1 的学生)可以将消息发送给学号为 2 的学生,随后该学生可以将消息发送给学号为 3 和 4 的学生。因此,所有学生都得知了学分相关信息。

输入解题思路,AI测评打分。不知道怎么写?

首页