#P1181. [CROATIAN2009]IZBROI选举

    ID: 189 传统题 1000ms 256MiB 尝试: 131 已通过: 52 难度: 8 上传者: 标签>CF2400提高+/省选-二分答案分组背包以值为状态消除被支配候选向下取整与向上取整直接模拟滚动数组

[CROATIAN2009]IZBROI选举

[COI2009] IZBORI

题目描述

有 VV 个选民在为选举投票。这次选举有 NN 个党派参加,他们要共同争夺议会的 MM 个席位。

假设党派编号为 11 至 NN,且他们分别获得 v1,v2,⋯ ,vnv_1,v_2,\cdots,v_n 票。席位分配如下:

  1. 所有获得少于 5%5\% 的票数的党派直接取消后续参选资格。
  2. 一开始议会不会为任何党派预留名额。
  3. 对于每个党派,计算 Qp=Vp÷(Sp+1)Q_p=V_p\div(S_p+1),其中 VpV_p 是党派获得的总票数,SpS_p 是已经分配给该党派的席位数量。
  4. QpQ_p 最大的党派会获得一个席位。(相同则编号小的获得)
  5. 重复第三四步直到满员。

现在已经清点了部分选票,知道了党派现在获得的票数,编写程序以求出在所有可能的情况下,各个党派可能获得的最多或最少席位。

输入格式

第一行三个正整数 V,N,MV,N,M。

第二行 NN 个正整数,为各个党派目前获得的票数,保证其总和不超过 VV。

输出格式

输出第一行 NN 个整数,为各个党派最多可能得到席位数。

输出第二行 NN 个整数,为各个党派最少可能得到席位数。

样例 #1

样例输入 #1

20 4 5
4 3 6 1

样例输出 #1

3 3 3 2
1 0 1 0

样例 #2

样例输入 #2

100 3 5
30 20 10

样例输出 #2

4 3 3
1 1 0

提示

正确输出第一行获得 20%20\% 的分数。正确输出第二行获得 80%80\% 的分数。

1≤V≤107,1≤N≤100,1≤M≤2001\le V\le 10^7,1\le N\le 100,1\le M\le 200。