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.
Definition
- Class:
- ChristmasBatteries
- Method:
- mostFun
- Parameters:
- int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int mostFun(int B, int N, int X, int Y, int Z, int M)
- (be sure your method is public)
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.
Examples
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.
2
12345
1
0
0
5
Returns: 4
7
77
2
1
2
11
Returns: 104
2
6
1
3
837
4
Returns: 5
6
61
36
819
0
757
Returns: 8127
7
12
16
38
460
400
Returns: 1178
4
16
236
101
9
49
Returns: 219
3
58
3
2
1
233
Returns: 1744
6
14
160
14
2
909
Returns: 3284
4
138
2
5
3
92
Returns: 1693
5
6
357
14
17
39
Returns: 92
7
4
229
601
385
945
Returns: 1737
7
6997
8
8
25
40
Returns: 35100
4
3150
9
45
43
45
Returns: 27158
3
38610
18
162
7
90
Returns: 54104
6
366
4
32
5
20
Returns: 404
7
270
10
100
8
50
Returns: 594
3
98
12
84
35
60
Returns: 735
7
98
12
84
35
60
Returns: 781
5
939800
95
760
117
475
Returns: 21991839
4
5
9
0
0
1000
Returns: 144
5
14
3
46
596
12
Returns: 36
7
1986
40
0
13
1
Returns: 0
0
174
66
25
6
3
Returns: 35
7
6
501
0
1
51
Returns: 113
1
548475
0
29
0
620
Returns: 33731444
3
20
20
2
7
53
Returns: 191
6
2156
6
2
4
10
Returns: 1740
3
15107
65
1
2
2
Returns: 0
4
7
1
0
448
8
Returns: 10
3
80
661
3
495
552
Returns: 6523
6
392
82
40
3
14
Returns: 633
0
58
26
12
1
8
Returns: 48
6
155698
12
759
2
1
Returns: 0
0
17888
756
2
30
449
Returns: 820080
6
29
0
8
31
50
Returns: 339
4
456
26
0
283
54
Returns: 2602
4
181
1
7
5
171
Returns: 3994
2
810
950
39
0
388
Returns: 33316
2
114428
426
154
1
15
Returns: 137333
0
86
7
941
11
3
Returns: 30
0
1145
13
9
602
546
Returns: 60754
4
811571
234
78
0
18
Returns: 973938
6
11
1
0
228
47
Returns: 260
3
670
4
1
675
174
Returns: 12763
7
1
1
48
1
1
Returns: 0
0
12
3
712
51
196
Returns: 232
5
6442
45
15
5
3
Returns: 2588
1
578
580
2
1
2
Returns: 117
0
129150
921
79
1
2
Returns: 25830
0
4735
367
552
499
289
Returns: 144512
2
39
0
0
24
1
Returns: 0
7
1
382
110
3
1
Returns: 0
6
27928
3
101
78
6
Returns: 11196
6
678
24
4
402
504
Returns: 36724
1
3683
0
10
4
58
Returns: 20746
2
36654
4
14
105
4
Returns: 14667
7
141
11
189
110
603
Returns: 11721
5
114931
0
396
216
39
Returns: 413928
2
1848
7
4
865
4
Returns: 187
2
24
6
1
0
74
Returns: 253
5
1586
28
36
1
60
Returns: 8923
2
6
649
3
719
836
Returns: 1771
1
391
0
26
31
2
Returns: 80
6
19
1
0
0
16
Returns: 37
2
98385
6
77
986
17
Returns: 177126
5
112
586
1
920
53
Returns: 772
0
4
715
994
179
53
Returns: 20
4
7735
30
1
3
248
Returns: 188126
1
14441
226
12
95
5
Returns: 3
2
51653
123
5
37
14
Returns: 72339
5
34
3
46
596
12
Returns: 70
7
45
40
0
13
1
Returns: 0
0
36
66
25
6
3
Returns: 8
7
44
9
6
501
1
Returns: 0
7
48
0
29
0
620
Returns: 5788
3
37
20
20
2
7
Returns: 26
1
46
53
6
2
4
Returns: 17
6
38
10
0
65
1
Returns: 0
0
38
2
2
7
1
Returns: 0
3
36
0
448
8
80
Returns: 232
4
50
661
3
495
552
Returns: 5140
6
47
82
40
3
14
Returns: 131
0
50
310
26
12
1
Returns: 0
4
38
8
12
759
2
Returns: 12
7
32
756
2
30
449
Returns: 3436
6
49
29
0
8
31
Returns: 297
4
40
50
25
26
283
Returns: 2230
3
33
54
181
1
7
Returns: 26
7
38
5
171
714
810
Returns: 6768
6
47
950
39
0
388
Returns: 4105
2
40
154
1
15
86
Returns: 381
5
36
7
941
11
3
Returns: 23
0
37
13
9
602
546
Returns: 2436
4
45
234
78
0
18
Returns: 96
6
48
11
1
0
228
Returns: 1988
5
39
47
2
355
4
Returns: 24
5
38
1
675
174
1
Returns: 0
7
38
1
48
1
1
Returns: 0
0
48
12
3
712
51
Returns: 220
5
48
196
45
15
5
Returns: 9
7
999999
889
779
988
987
Returns: 98342144
7
986371
973
927
963
997
Returns: 97857814
7
1000000
120
34
5
997
Returns: 96808503
7
10
145
281
827
961
Returns: 2427
3
750247
416
497
630
913
Returns: 68433047