← 返回题目列表

AtCoder · icpc2014spring_g

G. 比例代表制

中文机器翻译题面 查看原题

问题陈述

JAG王国举行了议会议员选举。 该国采用的唯一制度是政党名单比例代表制。 在这个系统中,每个公民投票给一个政党,一个政党赢得的席位数量将与其获得的选票数量成正比。 由于议会的席位总数是整数,当然,通常不可能精确地按比例分配席位。 在 JAG Kingdom 中,使用以下方法(称为 D'Hondt 方法)来确定每一方的席位数。

假设每个政党都有无限的候选人供应,并且每个政党的候选人都以某种方式排序。 对于获得 $x$ 票的政党的第 $y$ 候选人,分配值 $\dfrac{x}{y}$。 然后,所有候选者按照其指定值的降序排列。 第一个 $T$ 候选人被视为获胜,其中 $T$ 是席位总数, 一个政党赢得的席位数就是其获胜候选人的数量。

下表显示了三个参与方的示例。 第一方获得 40 美元选票,第二方获得 60 美元选票,第三方获得 30 美元选票。 如果席位总数为$T = 9$,则第一方将赢得$3$席位,第二方将赢得$4$席位,第三方将赢得$2$席位。

[原图]

选择获奖候选人时,通过抽签打破平局;任何平局的候选人都有机会获胜。 例如,在上面的示例中,如果 $T = 5$,则两个候选者的值是 $20$,并且有两种可能的结果:

  • 第一方赢得 $2$ 席位,第二方赢得 $2$ 席位,第三方赢得 $1$ 席位。

  • 第一方赢得 $1$ 席位,第二方赢得 $3$ 席位,第三方赢得 $1$ 席位。

您刚刚在电视上听到了选举结果。 知道有效选票总数和每个政党赢得的席位数后,您想知道每个政党获得了多少票。

给定 $N$、$M$ 和 $S_i$ ($1 \le i \le M$), 分别表示有效选票总数、政党数量以及第$i$个政党赢得的席位数, 您的任务是确定每个政党获得的最小和最大可能票数。 请注意,在某些情况下,给定的 $N$、$M$ 和 $S_i$ 可能不存在这种情况。


输入

输入的第一行包含两个整数 $N$ ($1 \le N \le 10^9$) 和 $M$ ($1 \le M \le 30{,}000$), 其中$N$是有效选票总数,$M$是政党数量。 接下来是 $M$ 行,其中第 $i$ 行包含单个整数 $S_i$ ($0 \le S_i \le 30{,}000$), 代表第 $i$ 党赢得的席位数。 您可以假设存在 $i$ 且 $S_i \ne 0$。

输出

如果不存在给定的$N$、$M$和$S_i$的情况,则显示“不可能”一词。 否则,输出 $M$ 行,每行包含两个整数。 第 $i$ 行中的第一个整数和第二个整数 应分别是第 $i$ 方获得的最小和最大可能票数。


示例输入 1

10 2
2
1

样本输入 1 的输出

5 7
3 5

示例输入 2

5 6
0
2
0
2
6
0

样本输入 2 的输出

0 0
1 1
0 0
1 1
3 3
0 0

示例输入 3

2000 5
200
201
202
203
204

样本输入 3 的输出

396 397
397 399
399 401
401 403
403 404

示例输入 4

15 10
1
1
1
1
1
1
1
1
1
13

样本输入 4 的输出

impossible

示例输入 5

1000000000 9
12507
16653
26746
21516
29090
10215
28375
21379
18494

样本输入 5 的输出

67611619 67619582
90024490 90033301
144586260 144597136
116313392 116323198
157257695 157269050
55221291 55228786
153392475 153403684
115572783 115582561
99976756 99985943