ChristmasBatteries
SRM 796 · 2020-12-21 · by misof
Problem Statement
Peter is very fond of his niece Emily. For Christmas, Peter wants to give his niece a collection of various toys. He has already purchased N toys. However, at the last moment Peter realized that he probably cannot give Emily all the toys.
The problem is that many of the toys require batteries, and those are not included in the package. Peter forgot to purchase batteries and now he could only find very few of them: he only has B batteries. And there's nothing worse than getting a toy that does not work because it lacks batteries. (Well, there are surely plenty of worse things, but not in Emily's world.)
Hence, Peter came to the following conclusion: he will only give Emily a subset of the toys he has purchased. The toys given to Emily must require at most B batteries in total.
The toys are numbered from 0 to N-1, inclusive. Toy i requires (i mod 5) batteries. The amount of fun from toy i is ((X*i*i + Y*i + Z) mod M).
The amount of fun from a collection of toys is simply the sum of amounts of fun from the individual toys in the collection. Find the collection of toys Peter should give Emily if he wants her to have as much fun as possible with the toys. Return the total amount of fun for that collection.
Notes
- Watch out for integer overflow when computing the amount of fun from a toy. In particular, we suggest computing the value X*i*i mod M as follows: (((X*i) mod M) * i) mod M.
- The reference solution does not depend on the properties of the formula used to compute the fun from a toy. The reference solution would find the correct subset for any values of fun from toys.
Constraints
- B will be between 0 and 7, inclusive.
- N will be between 1 and 10^6, inclusive.
- X, Y, Z will be between 0 and 999, inclusive.
- M will be between 1 and 1000, inclusive.
0 5 1 1 1 1000 Returns: 1
There are five toys. Peter has no batteries at all, so he can only give Emily toy 0 that requires no batteries at all. The fun from this toy is (1*0*0 + 1*0 + 1) mod 1000 = 1.
3 5 1 1 1 1000 Returns: 14
The same scenario as above, but now Peter has three batteries. Let's look at all the available toys: toy 0: requires 0 batteries, fun = 1 toy 1: requires 1 battery, fun = 3 toy 2: requires 2 batteries, fun = 7 toy 3: requires 3 batteries, fun = 13 toy 4: requires 4 batteries, fun = 21 Peter has multiple options what to give Emily. For example, he could give her toys 0, 1, and 2. However, we can easily verify that the best present are toys 0 and 3. These require a total of 3 batteries, and the total fun from them is 1 + 13 = 14.
3 5 1 1 1 13 Returns: 11
The same scenario as Example 1, but now the fun from toy 3 is zero and fun from toy 4 is only 8. Here the optimal solution is to give Emily toys 0, 1, and 2.
4 10000 123 456 789 1 Returns: 0
The fun from each toy is 0, so Peter's choice of presents does not matter at all. He can simply give Emily nothing.
7 4 3 5 7 997 Returns: 100
Peter has 7 batteries, his entire collection of toys only requires 6. Thus, he can give Emily all the toys.
2 12345 234 34 5 117 Returns: 143371
Watch out for integer overflow. For example, the fun from the very last toy in Peter's collection (toy 12344) is (234 * 12344 * 12344 + 34 * 12344 + 5) mod 117 = 22.
Submissions are judged against all 111 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChristmasBatteries with a public method int mostFun(int B, int N, int X, int Y, int Z, int M) · 111 test cases · 2 s / 256 MB per case