시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 185 | 23 | 17 | 44.737% |
A treasure is locked into a room of a well-guarded dungeon. At the door of the room, there is a magic scale and a set of N weights. The scale has an associated unknown target total weight W. We have the following properties:
One way to guarantee opening the door and reaching the coveted treasure is therefore to try all subsets of the N weights in order of increasing total weight. However, multiple subsets might have the same total weight, so a better strategy is to try one subset for each given total weight.
Help our adventurer by enumerating the first K possible total weights in increasing order, together with one corresponding subset of weights for each total weight.
K lines representing the first K possible total weights in increasing order, together with the corresponding weights. The format of each of the K lines is:
total_weight: weight_1 weight_2 ... weight_p
where weight_1 weight_2 ... weight_p
are p space-separated weights that sum to total_weight
(if there are multiple options, any will be accepted).
It is guaranteed that it will be possible to find at least K different weight sums given the input data.
5 10 1 12 4 5 100
0: 1: 1 4: 4 5: 1 4 6: 1 5 9: 4 5 10: 1 4 5 12: 12 13: 1 12 16: 4 12
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2020-2021 PA번