SixCandyBags | Topcoder Archive

Problem Statement

There is a vending machine that sells candy. It contains N distinct bags of candy, numbered 0 to N-1. Bag i contains candies[i] candies and costs price[i] cents.

You want to purchase exactly wantPieces of candy. You have exactly haveMoney cents.

You are aware that the vending machine is faulty: after the sixth purchase it becomes stuck and remains stuck until fixed by a technician. It's Sunday, so once you break the machine, that's it. Thus, you can purchase at most six bags of candy.

More expensive candies are fancier and taste better. Thus, if you can reach your main goal, you want to maximize the total cost of your purchase.

If you cannot purchase the exact right total number of candies, return -1. Otherwise, return the maximum cost of a valid way to purchase that many candies.

Definition

Class:: SixCandyBags
Method:: buy
Parameters:: int[], int[], int, int
Returns:: int
Method signature:: int buy(int[] candies, int[] price, int wantPieces, int haveMoney)
(be sure your method is public)

Constraints

candies will have between 1 and 100 elements, inclusive.
Each element of candies will be between 1 and 10^9, inclusive.
price will have the same number of elements as candies.
Each element of price will be between 1 and 10^9, inclusive.
wantPieces will be between 1 and 10^9, inclusive.
haveMoney will be between 1 and 10^9, inclusive.

Examples

```
{1, 2, 3, 4, 5, 6, 7}
```
```
{1, 2, 4, 8, 16, 32, 64}
```
```
27
```
```
123456789
```
```
Returns: 126
```
The only way to purchase 27 candies is to purchase the six biggest bags.

{1, 2, 3, 4, 5, 6, 7}

{1, 2, 4, 8, 16, 32, 64}

Returns: -1

Same test as before but you are one cent short.

```
{1, 2, 3, 4, 5, 6, 7}
```
```
{1, 2, 4, 8, 16, 32, 64}
```
```
9
```
```
40
```
```
Returns: 36
```
There are various ways to purchase a total of exactly 9 candies. The most expensive one would be to purchase bags with 7 and 2 candies, but you don't have enough money for that. The second best option is to purchase bags with 6+3 candies.
```
{1, 2, 3, 4, 5, 6, 7}
```
```
{1, 2, 4, 8, 16, 32, 64}
```
```
9
```
```
35
```
```
Returns: 35
```
Same test as the previous one, but now you cannot afford 6+3 either and you have to go for the purchase of 6+2+1 candies.
```
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
```
```
{8605, 32642, 16565, 6363, 24597, 22316, 25290, 11461, 18689, 16000}
```
```
5
```
```
80000
```
```
Returns: 79933
```
You have to purchase exactly 5 of these 10 bags. The closest you can get to 80000 cents is by purchasing bags with costs {16565, 6363, 22316, 18689, 16000}. Note that you cannot purchase the same bag multiple times. (If you could, it would be best to take five copies of the bag that costs 16000.)

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.