Connection Status:
Competition Arena > PieSharing

PieSharing

SRM 269 · 2005-10-26 · by Andrew_Lazarev

SRM 269 · 2005-10-26 · by Andrew_Lazarev · Dynamic Programming
Class Name: PieSharing
Return Type: int
Method Name: share
Arg Types: (vector<int>)
Problem Statement

Problem Statement

There are 3*N pie pieces arranged in a circle. You and Ted are going to eat the whole pie using the following rules. You can choose any piece and eat it, but Ted will eat its left and right neighbors (once a piece is eaten its left and right neighbors become neighbors themselves). This operation is repeated until the whole pie is eaten (in other words N times). You are planning to eat as big a part of the pie as possible.

You will be given int[] pieces. pieces[i] is the size of the i-th piece as a percentage (between 1 and 100). Return the maximum percentage of the pie that you can eat.

Constraints

  • pieces will have between 3 and 48 elements, inclusive.
  • The number of elements in pieces will be divisible by 3.
  • Each element in pieces will be between 1 and 100, inclusive.
  • The elements in pieces will sum up to 100.
Examples
0)
{33, 33, 34}
Returns: 34

You can eat the biggest piece.

1)
{5, 17, 22, 34, 18, 4}
Returns: 51

You can eat pieces with sizes 34 and 17.

2)
{11, 1, 1, 85, 1, 1}
Returns: 96

You will eat almost the whole pie.

3)
{6, 13, 14, 4, 14, 10, 1, 20, 18}
Returns: 48
4)
{1,2,13,1,1,44,1,36,1}
Returns: 93

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

Coding Area

Language: C++17 · define a public class PieSharing with a public method int share(vector<int> pieces) · 135 test cases · 2 s / 256 MB per case

Submitting as anonymous