KiwiJuice | Topcoder Archive

Problem Statement

Taro has prepared delicious kiwi fruit juice. He poured it into N bottles numbered from 0 to N-1. Each bottle has a capacity of C liters, and he poured bottles[i] liters of kiwi juice into the i-th bottle initially. Taro will sell these bottles after performing an arbitrary number of operations of the following type (possibly zero). In each operation, he chooses two distinct bottles A and B, and pours kiwi juice from bottle A to bottle B until either bottle A becomes empty or bottle B becomes full, whichever happens earlier.

If a bottle contains x liters of kiwi juice at the end (where x is an integer between 0 and C, inclusive), then Taro can sell the bottle for prices[x] dollars. Return the maximum amount of money he can earn.

Definition

Class:: KiwiJuice
Method:: theProfit
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int theProfit(int C, int[] bottles, int[] prices)
(be sure your method is public)

Constraints

C will be between 1 and 49, inclusive.
bottles will contain between 1 and 15 elements, inclusive.
Each element of bottles will be between 0 and C, inclusive.
prices will contain exactly C + 1 elements.
Each element of prices will be between 0 and 1,000,000, inclusive.

Examples

```
10
```
```
{5, 8}
```
```
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10}
```
```
Returns: 10
```
If Taro pours kiwi juice from bottle 0 to bottle 1, then bottle 0 will contain 3 liters of kiwi juice and bottle 1 will contain 10 liters of kiwi juice. He can sell bottle 1 for 10 dollars.

{5, 8}

{0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10}

Returns: 20

Sell both bottles without pouring.

```
10
```
```
{4, 5, 3, 7}
```
```
{14, 76, 12, 35, 6, 94, 26, 3, 93, 90, 420}
```
```
Returns: 625
```
It is possible that a bottle containing lesser juice is more expensive.
```
1
```
```
{0}
```
```
{1000000, 1000000}
```
```
Returns: 1000000
```

{2, 47, 24, 14, 0, 32, 9, 12, 31, 46, 39, 12, 16, 22, 29}

{428668, 995687, 128567, 37241, 496916, 238624, 304781, 997819, 85856, 417008,
398570, 951499, 750349, 333625, 927594, 188616, 942498, 259414, 654344, 354809,
25303, 226854, 98578, 207140, 305527, 358343, 393213, 256248, 282644, 103327,
667191, 103402, 609183, 619323, 189127, 518006, 778846, 400460, 128334, 795097,
605203, 669142, 121825, 934404, 837430, 554265, 610818, 546228, 80784, 949440}

Returns: 12873962

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.