CollectingStamps | Topcoder Archive

Problem Statement

You are a proud owner of a large and diverse collection of post stamps. There are stamps from N different countries in your collection. For simplicity, countries are numbered 0 through N-1. The number of stamps from country i that you have is given by count[i].

You would like to extend your collection further. It is known that one stamp from country i can be sold at local market for sell[i] dollars and it can be bought for buy[i] dollars. The local market has a sufficient supply of stamps from each country. Initially you have no money at all, so you will need to sell at least one stamp before being able to buy any stamps.

You are allowed to perform arbitrarily many buy and sell operations. The only limitation is that you need to have enough money for each buy operation that you perform. There are no other limitations on the operations you are allowed to perform. In particular, it is allowed for your collection to contain stamps from fewer than N countries.

Return the maximum total number of stamps that your collection can have.

Definition

Class:: CollectingStamps
Method:: maximumCount
Parameters:: int[], int[], int[]
Returns:: int
Method signature:: int maximumCount(int[] count, int[] sell, int[] buy)
(be sure your method is public)

Constraints

count, sell and buy will each contain between 1 and 50 elements, inclusive.
count, sell and buy will contain the same number of elements.
Each element of count will be between 1 and 100, inclusive.
Each element of sell will be between 1 and 99, inclusive.
For each i, buy[i] will be between sell[i] + 1 and 100, inclusive.

Examples

```
{100,100}
```
```
{1,99}
```
```
{2,100}
```
```
Returns: 5050
```
Initially, you have 100 stamps from country 0 and 100 stamps from country 1. Each stamp from country 1 can be sold for 99 dollars. Your best course of actions is to sell all your stamps from country 1 for a total of 9900 dollars. You can then use this money to buy 4950 stamps from country 0 for 2 dollars each. At the end, your collection will have 100 + 4950 = 5050 stamps, all from country 0.
```
{1,2,3,4,5}
```
```
{5,4,3,2,1}
```
```
{6,7,8,9,10}
```
```
Returns: 15
```
Your collection originally has 15 stamps and in this case buy/sell operations will not help you extend it.

{6,6,2,4,10,4,4,8,1,6}

{5,5,2,12,10,6,4,4,5,4}

{7,16,13,18,11,15,8,9,18,10}

Returns: 58

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

{12,5,12,4,6,2,2,2,2,3,2,5,3,19,15,8,4,5}

{19,16,17,20,19,17,15,5,10,18,8,17,10,22,20,17,6,20}

Returns: 63

{28,29,32,32,33,26,6,6,31,14,12,19,20,29,15,20,25,30,13,24,30,14,24,22,
 1,4,21,17,4,14,25,23,9,25,25,4,19,8,29,16,18,22,20,9,9,18,18,9,8,10}

{17,83,12,21,53,21,12,7,23,82,77,16,9,28,49,25,17,42,45,82,50,9,15,64,79,
 34,4,40,69,21,40,2,24,53,9,63,8,21,55,26,5,43,55,25,42,3,23,17,10,8}

{85,90,20,36,88,46,18,88,100,99,86,34,50,93,61,41,98,75,53,96,84,91,59,99,99,
 39,15,91,99,72,83,12,37,75,14,66,38,69,99,98,12,92,78,79,89,63,42,48,40,42}

Returns: 2565

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.