CollectingCoins
SRM 778 · 2020-02-13 · by jy_25
Problem Statement
We have a machine that can produce different types of coins. For each type you are given the value v[i] those coins have. (Different types of coins may have the same value.) Each day we can use the machine to produce as many coins as we wish, but there are some restrictions we must obey:
- No two coins produced on the same day can have the same type. (In other words, you can produce at most one coin of each type each day.)
- For each coin type i there is a constant d[i] with the following meaning: among any d[i] consecutive days there must be at least one day on which a coin of type i is not produced.
- Among any k consecutive days there must be at least one day when the machine is powered down and does not produce any coins at all.
You are given the
Constraints
- v and d will have the same number of elements.
- The number of elements in v will be between 1 and 1000, inclusive.
- Each element of v will be between 1 and 1000, inclusive.
- k will be between 2 and 1000, inclusive.
- Each element of d will be between 2 and 10 9 , inclusive.
- m will be between 1 and 10 9 , inclusive
5
3
{1}
{3}
Returns: 4
We have 5 days. The machine must be idle at least once in each 3-day interval. There is one type of coins. Their value is 1, and in each 3-day interval there has to be a day on which coins of this type are not produced. The optimal solution is to produce one coin on each of days 1, 2, 4, and 5, and to do nothing on day 3.
5
4
{1, 2}
{2, 3}
Returns: 10
There are two types of coins. To generate coins with a total value of 10, we can do the following: On day 1, generate both types of coins. On day 2, generate only second type. On day 3, don't generate any coin. On day 4, generate both types of coins. On day 5, generate only second type. This way we have produced 2 coins of the first type and 4 coins of the second type. Their total value is 2*1 + 4*2 = 10. There is no better solution.
921047330
132
{266}
{31}
Returns: 237095409516
952233580
255
{255}
{48}
Returns: 237760822155
417316517
995
{233}
{302}
Returns: 96912779275
10
17
{10,20}
{30,40}
Returns: 300
Given how small m is, we can generate both coin types each day.
Submissions are judged against all 114 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CollectingCoins with a public method long long maxValue(int m, int k, vector<int> v, vector<int> d) · 114 test cases · 2 s / 256 MB per case