251 . 小風愛球球
TopCoder
Tags
Description
小風愛球球，小風甚至有 $n$ 種顏色的球，第 $i$ 種顏色的球有 $a_i$ 個。給定 $k$，從所有 $\sum_{i = 1}^ {n}a_i$ 個球裡隨機選 $k$ 個，將選出來的 $k$ 顆球記在 $b$ 陣列裡（被選出的第 $i$ 種顏色的球有 $b_i$ 個）。求最有可能出現的 $b$ 的長相，若有多組解請輸出字典序最小的一種。
Input Format
第一行有兩個正整數 $n, k$ 代表顏色的數量以及要拿的球的個數。
第二行有 $n$ 個數字 $a_1, a_2, \cdots , a_n$ 代表每種顏色的球的數量。
- $1 \leq n \leq 10^ 3$
- $1 \leq k \leq 10^ 9$
- $1 \leq a_i \leq 10^ 9$
- $k \leq \sum_{i = 1}^ {n} a_i$
Output Format
輸出 $n$ 個數字代表出現機率最高的球的顏色的分布。若有多種可能，輸出之中字典序最小的一種。
Sample Input 1
15 13
2 10 7 6 1 3 8 6 10 1 4 7 3 9 3
2 10 7 6 1 3 8 6 10 1 4 7 3 9 3
Sample Output 1
0
2
1
1
0
0
2
1
2
0
1
1
0
2
0
2
1
1
0
0
2
1
2
0
1
1
0
2
0
Hints
Problem Source
IOICamp 2020 Day3 pF
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~50 | 無額外限制 | 100 |