Connection Status:
Competition Arena > ColorfulCookie

ColorfulCookie

SRM 528 · 2011-05-25 · by ir5

SRM 528 · 2011-05-25 · by ir5 · Advanced Math, Dynamic Programming
Class Name: ColorfulCookie
Return Type: int
Method Name: getMaximum
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

Little Fox Jiro received a box from his sister Fox Ciel as a present. The box contained many cookies of various colors. Jiro wants to eat as many of these cookies as possible.

The cookies are locked in a strange box. Jiro cannot take cookies from the box directly. On the box there is a dial and a button. These can be used to obtain cookies in the following way:

  1. Jiro uses the dial to choose any pair of distinct colors C1 and C2.
  2. Jiro pushes the button. If there are less than P1 cookies of color C1, nothing happens. Also, if there are less than P2 cookies of color C2, nothing happens. Otherwise, exactly P1 cookies of color C1 and exactly P2 cookies of color C2 drop out of the box and Jiro eats all of them.

You are given a int[] cookies describing the initial contents of the box: for each i, the box contains cookies[i] cookies of color i. You are also given the ints P1 and P2. Your method must return the maximum number of cookies Jiro can eat by repeating above procedure optimally.

Constraints

  • cookies will contain between 1 and 50 elements, inclusive.
  • Each element of cookies will be between 1 and 2,000, inclusive.
  • P1 and P2 will each be between 50 and 2,000, inclusive.
Examples
0)
{100, 100}
50
50
Returns: 200

The optimal solution is to select colors 0 and 1 and to push the button twice: each time obtaining 50 cookies of each color.

1)
{50, 250, 50}
50
100
Returns: 300

An optimal solution: Pick colors 0 and 1 (note that order matters) and push the button to obtain 50 cookies of color 0 and 100 cookies of color 1. Pick colors 2 and 1 (again, note the order) and push the button to obtain 50 cookies of color 2 and 100 cookies of color 1. This gives Jiro a total of 300 cookies. Note that 50 cookies of color 1 remained in the box, but there is no way to get them out.

2)
{2000}
100
200
Returns: 0

In this case all cookies have the same color. It is impossible to obtain any of them.

3)
{123, 456, 789, 555}
58
158
Returns: 1728
4)
{1, 1, 1, 1, 1, 1, 1}
2000
2000
Returns: 0

all one

64)
{2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000}
50
50
Returns: 100000

the worst case

71)
{1970, 1963, 1966, 1967, 1971, 1969, 1972, 1971, 1970, 1967, 1969, 1968, 1967, 1971, 1969, 1974, 1967, 1964, 1972, 1972, 1971, 1968, 1968, 1970, 1970, 1975, 1970, 1965, 1970, 1976, 1968, 1966, 1965, 1967, 1969, 1968, 1974, 1966, 1973, 1972, 1968, 1969, 1975, 1969, 1967, 1968, 1973, 1974, 1970, 1972}
50
51
Returns: 98475

case where it's possible to eat all cookies

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

Coding Area

Language: C++17 · define a public class ColorfulCookie with a public method int getMaximum(vector<int> cookies, int P1, int P2) · 133 test cases · 2 s / 256 MB per case

Submitting as anonymous