Connection Status:
Competition Arena > TaroCutting

TaroCutting

SRM 642 · 2014-08-25 · by Witaliy

SRM 642 · 2014-08-25 · by Witaliy · Brute Force, Recursion
Class Name: TaroCutting
Return Type: int
Method Name: getNumber
Arg Types: (vector<int>, vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Cat Taro has some trees in his garden. Initially, the i-th tree (0-based index) is height[i] meters tall. Each day the trees grow. For each i, the i-th tree will grow by exactly add[i] meters during each day.

Taro wants cut the trees and he has some devices to do that. For each valid i, the i-th device (0-based index) will cut any chosen tree with height greater than device[i] meters to exactly device[i] meters.

At the end of each day, Taro can choose any (possibly empty) subset of trees and cut them. There are two restrictions:

  • Each tree can be cut at most once per day.
  • Each device can be used at most once per day.

You are given the int[]s height, add and device, and an int time. Return the smallest possible sum of the heights of the trees after time days (i.e., time iterations of "the trees grow and then Taro cuts some of them").

Constraints

  • height will contain between 1 and 150 elements, inclusive.
  • height and add will contain the same number of elements.
  • device will contain between 1 and 150 elements, inclusive.
  • Each element of height, add and device will be between 0 and 10,000, inclusive.
  • time will be between 1 and 150, inclusive.
Examples
0)
{4, 7}
{7, 1}
{7}
1
Returns: 15

There are two trees. Tree 0 starts 4 meters tall and grows by 7 meters each day. Tree 1 starts 7 meters tall and grows by 1 meter each day. Thus, during the first day the first tree will grow to 4+7 = 11 meters and the second tree will grow to 7+1 = 8 meters. Taro has a single tree-cutting device that cuts a tree to 7 meters. As both trees now have more than 7 meters, he can use it on either of them. In order to minimize the sum of heights of trees, it is better to cut the taller tree: tree 0. After the cutting, the total height of trees will be 7+8 = 15 meters.

1)
{3, 1, 2}
{1, 1, 1}
{7, 7, 7}
2
Returns: 12

After two days the trees' heights will be 5, 3, and 4. The trees are still too short so Taro is unable to cut anything.

2)
{100, 50}
{75, 30}
{200, 100, 50}
2
Returns: 130
3)
{7, 10, 1, 7, 5, 4, 11, 5, 7, 9, 10, 8}
{1, 3, 4, 10, 2, 1, 6, 4, 8, 7, 5, 10}
{7, 1, 5, 10}
3
Returns: 96
4)
{7, 10, 1, 7, 5, 1}
{1, 3, 4, 10, 2, 2}
{1}
1
Returns: 37

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TaroCutting with a public method int getNumber(vector<int> height, vector<int> add, vector<int> device, int time) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous