[COI 2009] IZBORI

Luogu

IDLGP8364

Time1000ms

Memory128MB

DifficultyP6

2009COI（克罗地亚）

有 $V$ 个选民在为选举投票。这次选举有 $N$ 个党派参加，他们要共同争夺议会的 $M$ 个席位。假设党派编号为 $1$ 至 $N$，且他们分别获得 $v_1,v_2,\cdots,v_n$ 票。席位分配如下： 1. 所有获得少于 $5\%$ 的票数的党派直接取消后续参选资格。 2. 一开始议会不会为任何党派预留名额。 3. 对于每个党派，计算 $Q_p=V_p\div(S_p+1)$，其中 $V_p$ 是党派获得的总票数，$S_p$ 是已经分配给该党派的席位数量。 4. $Q_p$ 最大的党派会获得一个席位。（相同则编号小的获得） 5. 重复第三四步直到满员。现在已经清点了部分选票，知道了党派现在获得的票数，编写程序以求出在所有可能的情况下，各个党派可能获得的最多或最少席位。 ## Input 第一行三个正整数 $V,N,M$。第二行 $N$ 个正整数，为各个党派目前获得的票数，保证其总和不超过 $V$。 ## Output 输出第一行 $N$ 个整数，为各个党派最多可能得到席位数。输出第二行 $N$ 个整数，为各个党派最少可能得到席位数。 [samples] ## Note 正确输出第一行获得 $20\%$ 的分数。正确输出第二行获得 $80\%$ 的分数。 $1\le V\le 10^7,1\le N\le 100,1\le M\le 200$。

Samples

Input #1

20 4 5
4 3 6 1

Output #1

3 3 3 2
1 0 1 0

Input #2

100 3 5
30 20 10

Output #2

4 3 3
1 1 0

API Response (JSON)

{
  "problem": {
    "name": "[COI 2009] IZBORI",
    "description": {
      "content": "有 $V$ 个选民在为选举投票。这次选举有 $N$ 个党派参加，他们要共同争夺议会的 $M$ 个席位。 假设党派编号为 $1$ 至 $N$，且他们分别获得 $v_1,v_2,\\cdots,v_n$ 票。席位分配如下： 1. 所有获得少于 $5\\%$ 的票数的党派直接取消后续参选资格。 2. 一开始议会不会为任何党派预留名额。 3. 对于每个党派，计算 $Q_p=V_p\\div(S_p+1)",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8364"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $V$ 个选民在为选举投票。这次选举有 $N$ 个党派参加，他们要共同争夺议会的 $M$ 个席位。\n\n假设党派编号为 $1$ 至 $N$，且他们分别获得 $v_1,v_2,\\cdots,v_n$ 票。席位分配如下：\n\n1. 所有获得少于 $5\\%$ 的票数的党派直接取消后续参选资格。\n\n2. 一开始议会不会为任何党派预留名额。\n\n3. 对于每个党派，计算 $Q_p=V_p\\div(S_p+1)...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments