Cows in a Skyscraper
플래티넘 II의견: 0
A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don't like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.
The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.
Line 1: N and W separated by a space.
Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.
Line 1: A single integer, R, indicating the minimum number of elevator rides needed.
Lines 2..1+R: Each line describes the set of cows taking one of the R trips down the elevator. Each line starts with an integer giving the number of cows in the set, followed by the indices of the individual cows in the set.
(This problem has multiple valid outputs; any minimal valid set of rides is accepted by a special judge.)
skyscraper.inskyscraper.out4 10
5
6
3
73
2 1 3
1 2
1 4Input details: There are four cows weighing 5, 6, 3, and 7 pounds. The elevator has a maximum weight capacity of 10 pounds.
Output details: We can put the cow weighing 3 on the same elevator as any other cow but the other three cows are too heavy to be combined. Several other solutions are possible for this input.
평가 및 의견
Cows in a Skyscraper
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cows in a Skyscraper