Problem Statement
You have C pieces of strawberry candy.
You are in charge of some kids. L of them love strawberries, and the remaining D of them don't care about strawberries. (The total number of kids is therefore L + D.)
You have decided to distribute as many candies as possible among the kids. You want to do it according to the following rules:
- Each kid must get at least 1 piece of candy.
- Each kid must get at most 100,000 pieces of candy.
- Each kid that loves strawberries must get the same number of candies.
- Each kid that does not care about strawberries must get the same number of candies.
- If there are kids of both types (i.e., if both L and D are positive) a kid that loves strawberries must get strictly more candies than a kid that does not care about them.
If your goal cannot be achieved at all (there is no valid way to distribute candies), return -1. Otherwise, return the smallest possible number of candies left over (i.e., not given to any child).
Definition
- Class:
- DividingCandy
- Method:
- divide
- Parameters:
- long, long, long
- Returns:
- long
- Method signature:
- long divide(long C, long L, long D)
- (be sure your method is public)
Constraints
- C will be between 1 and 10^12, inclusive.
- L will be between 0 and 10^12, inclusive.
- D will be between 0 and 10^12, inclusive.
- L+D will not be zero.
Examples
80
10
10
Returns: 0
You have 80 strawberry candies. There are 10 kids who love strawberries and 10 kids who don't care about them. One optimal solution is to give each of the first 10 kids 5 candies and to give each of the other 10 kids 3 candies. This way you have handed out all the candies and you have none left.
27
20
10
Returns: -1
Remember that each kid must get at least one piece of candy.
1234
15
55
Returns: 4
Here it's not possible to hand out all the candies, and it's quite easy to show that you will always have at least 4 candies left over.
1
1
0
Returns: 0
The only child gets the only piece of candy. (This particular child loves strawberries, but that does not really matter here.)
9876543210
0
2
Returns: 9876343210
Remember that each kid can only get up to 100,000 candies. Here the best you can do is to give each kid exactly 100,000 of your candies. You will still have quite many candies left over.
1234567
2323
4747
Returns: 44
9876543210
47
0
Returns: 9871843210
9876543210
987654322
0
Returns: 987654312
98765436210
0
9876543627
Returns: 9876543567
37
14
10
Returns: -1
38
14
10
Returns: 0
4718803
255999072
104554406420
Returns: -1
5955217264
550195858414
128654
Returns: -1
1945526
24174
15092312079
Returns: -1
398384431
6
404568667768
Returns: -1
2507971
14823990
5380883297
Returns: -1
1310277910
55499601715
4530769
Returns: -1
1744200488
123607717077
94494
Returns: -1
390160982005
33064496
85092
Returns: 3021
276590639
1193
24
Returns: 154890663
6643732625
232351988
7815141
Returns: 5019564
1500396267
306
432
Returns: 1426596699
10275110721
247443
1
Returns: 0
76123533
8736258
71002
Returns: 5736455
348
11026628440
858
Returns: -1
962335677241
133
51
Returns: 962317277292
12
42677
41106422055
Returns: -1
113779069471
60621724973
114587400
Returns: -1
1037309
309837446424
7674493017
Returns: -1
3
81459717906
519151
Returns: -1
5347748357
2797255
561131087
Returns: 505295
145679774010
54458466688
6
Returns: 36762840628
32137878921
19
15457231292
Returns: 1221516337
31403499570
103
55885287
Returns: 41553563
29361437743
75
9231579
Returns: 73
4668061
51533808
93141
Returns: -1
371828
858471555
504901299
Returns: -1
1163439
1003
1
Returns: 0
257000819
13991809919
102
Returns: -1
171
224588210
3977126227
Returns: -1
50010
1096951
532221575652
Returns: -1
745427280678
5
751314807273
Returns: -1
75198252
31513
3677
Returns: 10
1
33531870
58
Returns: -1
81102786
2017018460
325681582817
Returns: -1
55525680
187003764
1881390
Returns: -1
20
2536895
129166
Returns: -1
54
3
639933410528
Returns: -1
389313310096
8457999347
6895788789
Returns: 513657578
51807822339
556086870012
248562113792
Returns: -1
334094676520
2366812
1240
Returns: 97289477760
44775
41
5005396920
Returns: -1
40
168999715325
106686299
Returns: -1
49995724284
5
42830565591
Returns: 7164658693
1948185
6180981859
6770
Returns: -1
14
120
106
Returns: -1
150058730
2883476
22891
Returns: 3523
679
12
4
Returns: 3
110712
5857
14607666
Returns: -1
359
286978148
81979605
Returns: -1
246507517
8369982
71486
Returns: 1776431
237379
8
46354791
Returns: -1
13265930331
304824124
31
Returns: 158491697
147942
1443
30215
Returns: 844
1497768131
265257
131
Returns: 3
93454
31665376822
13638
Returns: -1
36127049
17212003274
3
Returns: -1
11
8604368869
36885789034
Returns: -1
32347735
4831
234731
Returns: 46
5789029456
25
445449585854
Returns: -1
15
973634708
117239125
Returns: -1
112
22696922
277763
Returns: -1
2
370
32
Returns: -1
249009784
123887855
174949255841
Returns: -1
896
34339595178
84877
Returns: -1
17
155169726072
2
Returns: -1
160
871642702213
72458708332
Returns: -1
1322
20227
803
Returns: -1
499544272096
265041149
3899995326
Returns: 5665180
3669764
55393659707
58818919
Returns: -1
6
990
40355407
Returns: -1
236369003254
1
5536424
Returns: 2353422
596395912658
131657817
198221
Returns: 33410
3811559
806935087318
390959
Returns: -1
902939807
881
165
Returns: 798339972
2979
23801956402
22546479
Returns: -1
2878852627
7394
1775510286
Returns: 363942341
51860222747
81
233175
Returns: 28534855922
193
40191032205
29267708
Returns: -1
393708
453765892234
108265206722
Returns: -1
443027738
228751816950
155889
Returns: -1
200001
1
1
Returns: 2
The best you can do here is to give 100,000 candies to the kid who loves strawberries and 99,999 candies to the kid who doesn't.
9
10
0
Returns: -1
1000000000000
0
1
Returns: 999999900000
2
1
1
Returns: -1
14
5
5
Returns: -1
9
2
1
Returns: 0
1
0
10
Returns: -1
100
0
1
Returns: 0
7
5
1
Returns: -1
6
2
1
Returns: 1
8
2
3
Returns: 1