TheProgrammingContestDivTwo
SRM 502 · 2010-11-01 · by rng_58
SRM 502 · 2010-11-01 · by rng_58 · Greedy, Simple Search, Iteration
Problem Statement
Problem Statement
Farmer John and Fox Brus are participating in a programming contest as a team.
The duration of the contest is T minutes and they are given N tasks. Solutions can be submitted at any time during the contest, including exactly T minutes after the start of the contest. It takes them requiredTime[i] minutes to solve the i-th task.
The score in this contest is represented by two numbers, solved and penalty. Initially both numbers are 0. If they solve a task t minutes after the start of the contest, solved increases by 1 and penalty increases by t. Two scores are compared by solved first. If two scores have different solved, the score with bigger solved is better. If two scores have the same solved, the score with smaller penalty is better.
Return aint[] containing exactly two integers that describes the best score they can get. The first integer of the return value must represent solved and the second integer must represent penalty.
The duration of the contest is T minutes and they are given N tasks. Solutions can be submitted at any time during the contest, including exactly T minutes after the start of the contest. It takes them requiredTime[i] minutes to solve the i-th task.
The score in this contest is represented by two numbers, solved and penalty. Initially both numbers are 0. If they solve a task t minutes after the start of the contest, solved increases by 1 and penalty increases by t. Two scores are compared by solved first. If two scores have different solved, the score with bigger solved is better. If two scores have the same solved, the score with smaller penalty is better.
Return a
Constraints
- T will be between 1 and 100,000, inclusive.
- requiredTime will contain between 1 and 50 elements, inclusive.
- Each element of requiredTime will be between 1 and 100,000, inclusive.
Examples
0)
74
{47}
Returns: {1, 47 }
They can solve the task. solved will be 1 and penalty will be 47.
1)
74
{4747}
Returns: {0, 0 }
They don't have time enough to solve the task.
2)
47
{8, 5}
Returns: {2, 18 }
The order is important. If they solve task 0 first and task 1 second, solved will be 2 and penalty will be 21. If they solve task 1 first and task 0 second, solved will be 2 and penalty will be 18.
3)
47
{12, 3, 21, 6, 4, 13}
Returns: {5, 86 }
4)
58
{4, 5, 82, 3, 4, 65, 7, 6, 8, 7, 6, 4, 8, 7, 6, 37, 8}
Returns: {10, 249 }
Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheProgrammingContestDivTwo with a public method vector<int> find(int T, vector<int> requiredTime) · 47 test cases · 2 s / 256 MB per case