BunnyComputer
SRM 487 · 2010-03-12 · by lyrically
SRM 487 · 2010-03-12 · by lyrically · Simple Math, Simple Search, Iteration
Problem Statement
Problem Statement
Bunnies like programming and they often practice for contests.
There is a special computer named B-Computer, which all bunnies are eager to use. All bunnies want to solve a difficult problem using B-Computer. Because they type very fast, each of them wants to solve the problem according to the following process that consists of 3 stages (no delay is allowed between subsequent stages):
A day is divided into a number of equal time units, and each time unit has an associated positive integer value called preference. You are given aint[] preference, which contains the preference values for a day.
The number of elements in preference is the number of time units in the day,
and the i-th element of preference is the preference of the i-th time unit.
Bunnies want to design a B-Computer schedule for a single day so that the sum of preferences of time units in which one of them uses B-Computer is maximized. The schedule must be such that each bunny uses B-computer exactly as described above and both time units at which the same bunny uses B-computer are in the same day. Return the maximum possible sum of preferences. You can assume that there are infinitely many bunnies.
There is a special computer named B-Computer, which all bunnies are eager to use. All bunnies want to solve a difficult problem using B-Computer. Because they type very fast, each of them wants to solve the problem according to the following process that consists of 3 stages (no delay is allowed between subsequent stages):
- Use B-Computer for exactly one time unit.
- Think and calculate on paper for exactly k time units, not using B-Computer.
- Use B-Computer for exactly one time unit again to complete.
A day is divided into a number of equal time units, and each time unit has an associated positive integer value called preference. You are given a
Bunnies want to design a B-Computer schedule for a single day so that the sum of preferences of time units in which one of them uses B-Computer is maximized. The schedule must be such that each bunny uses B-computer exactly as described above and both time units at which the same bunny uses B-computer are in the same day. Return the maximum possible sum of preferences. You can assume that there are infinitely many bunnies.
Constraints
- preference will contain between 1 and 50 elements, inclusive.
- Each element of preference will be between 1 and 1,000,000, inclusive.
- k will be between 1 and 50, inclusive.
Examples
0)
{ 3, 1, 4, 1, 5, 9, 2, 6 }
2
Returns: 28
The sum is maximized when three bunnies use B-Computer as follows: One bunny uses B-Computer during the 1-st time unit and again during the 4-th time unit. One bunny uses B-Computer during the 3-rd time unit and again during the 6-th time unit. One bunny uses B-Computer during the 5-th time unit and again during the 8-th time unit.
1)
{ 3, 1, 4, 1, 5, 9, 2, 6 }
1
Returns: 31
2)
{ 1, 2, 3, 4, 5, 6 }
3
Returns: 14
3)
{ 487, 2010 }
2
Returns: 0
No bunnies can use B-Computer.
4)
{ 1, 4, 2 }
1
Returns: 3
Submissions are judged against all 216 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BunnyComputer with a public method int getMaximum(vector<int> preference, int k) · 216 test cases · 2 s / 256 MB per case