시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 1024 MB | 66 | 19 | 16 | 28.571% |
During the renovation of your garden, you decide that you want a gravel path running from the street to your front door. Being a member of the Boulders And Pebbles Community, you want this path to look perfect. You already have a regular grid to put the gravel in, as well as a large container of gravel containing exactly as much as the total capacity of the grid.
There is one problem: the gravel does not yet fit perfectly into the grid. Each grid cell has the same (fixed) capacity and every piece of gravel has a certain weight. You have a grindstone that can be used to split the stones into multiple pieces, but doing so takes time, so you want to do a minimal number of splits such that the gravel can be exactly distributed over the grid.
As an example, consider the first sample case. There are three grid cells of size $8$, which can be filled as follows. Put the stones of weight $2$ and $6$ in the first cell. Now grind the stone of weight $7$ into two pieces of weight $3$ and $4$. Then the other two grid cells get filled by weights $3, 5$ and $4, 4$ respectively.
The input consists of:
It is guaranteed that $w_1 + w_2 + \dots + w_n$ is a multiple of $k$.
Output the minimal number of times a stone needs to be split into two, such that all the pieces of gravel can be used to fill all the grid cells perfectly.
5 8 2 4 5 6 7
1
2 5 12 13
4
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2022 G번