Problem Statement
You have just opened a new gym. There are M workout machines at the gym.
You are expecting N visitors. We will number them from 0 to N-1 in order of arrival. The visitors will be arriving at 1-second intervals. (I.e., visitor number x will arrive precisely x seconds after visitor 0.)
Each visitor will behave as follows:
- If there is at least one currently unused workout machine: pay an entry fee, choose one arbitrary machine, use it for some number of seconds, then go home.
- Otherwise: turn around and go home immediately.
If visitor number i enters your gym, they will stay there for exactly 0.5 + (i*i modulo T) seconds.
Return the number of visitors who will pay the entry fee.
Definition
- Class:
- Gym
- Method:
- calculateProfit
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int calculateProfit(int M, int N, int T)
- (be sure your method is public)
Notes
- Watch out for integer overflow when calculating (i*i modulo T).
Constraints
- M will be between 1 and 300,000, inclusive.
- N will be between 1 and 300,000, inclusive.
- T will be between 1 and 1,000,000, inclusive.
Examples
47
10
1000
Returns: 10
Plenty of workout machines for everyone.
1
10
1000
Returns: 3
We only have a single workout machine. The following is going to happen: Client 0 will arrive at time 0, start using a machine, then depart at time 0.5. Client 1 will arrive at time 1, start using a machine, then depart at time 2.5. While client 1 uses the machine, client 2 arrives, sees that there are no machines available, and turns around. Client 3 will arrive at time 3 and use the machine while all the remaining clients arrive and turn around.
1
10
1
Returns: 10
We still have only one workout machine, but now everyone just uses it for 0.5 seconds and leaves before the next client arrives.
15
100
47
Returns: 82
128654
294877
56300
Returns: 294877
6
293943
94494
Returns: 55
85092
258181
1
Returns: 258181
24
267008
3972
Returns: 3595
81
295737
247443
Returns: 334
1
254272
27
Returns: 18838
3
205466
348
Returns: 4144
133
211611
580797
Returns: 342
42677
272080
6
Returns: 272080
19
268270
103
Returns: 102241
13
276393
93141
Returns: 116
1003
200080
3
Returns: 200080
102
216233
31513
Returns: 1585
3677
200585
58
Returns: 200585
129166
212151
355083
Returns: 191311
1
279829
57285
Returns: 14
1240
231324
41
Returns: 231324
40
277215
234
Returns: 98346
5
273280
425
Returns: 6440
6770
206431
106
Returns: 206431
4312
270768
12
Returns: 270768
4
233578
7761
Returns: 272
71486
294903
25250
Returns: 294903
7514
248082
21
Returns: 248082
11918
255325
265257
Returns: 30687
131
232912
3
Returns: 232912
4
250259
4831
Returns: 467
234731
266874
15
Returns: 266874
112
249475
3259
Returns: 16662
2
275381
1
Returns: 275381
896
270633
5
Returns: 270633
160
280234
1322
Returns: 68731
6
218565
77
Returns: 28407
1
246038
1105
Returns: 672
784
233574
165
Returns: 233574
6
249857
81
Returns: 43185
155889
238609
8812
Returns: 238609
28
285071
2
Returns: 285071
117
239452
11853
Returns: 5049
52
259586
10116
Returns: 2716
73317
209951
125465
Returns: 209951
35488
203851
2691
Returns: 203851
17
251233
311397
Returns: 81
24
280202
1519
Returns: 9449
3533
230176
15952
Returns: 105409
3
201209
35776
Returns: 42
1512
236124
109708
Returns: 7737
5
232052
284148
Returns: 25
60
236148
102
Returns: 236148
8150
281789
258713
Returns: 23390
2
10
100
Returns: 5
This test case is also similar to Example #1, but this time we have two machines: a rowing machine and a treadmill. Client 0 arrives at time 0. Both machines are available. Client 0 selects and starts using the rowing machine machine, then departs at time 0.5. Client 1 arrives at time 1. Both machines are available. Client 1 selects and starts using the treadmill. Client 2 arrives at time 2. Only the rowing machine is available, so they start using the rowing machine. At time 2.5 client 1 departs. Client 3 arrives at time 3. Only the treadmill is available, so client 3 starts using that. Client 4 arrives at time 4. Nothing is available. Client 5 arrives at time 5. Nothing is available. Client 6 arrives at time 6. Nothing is available. At time 6.5 client 2 departs and the rowing machine is now available. Client 7 arrives at time 7 and starts using the rowing machine. Clients 8 and 9 both leave as there are no machines available for them.
15
100
47
Returns: 82
47
300000
1000
Returns: 29311
300000
300000
1000000
Returns: 300000
3000
300000
9876
Returns: 186318
50000
300000
50000
Returns: 300000
2
300000
300000
Returns: 14
200000
300000
1000000
Returns: 243345
150
299999
12345
Returns: 7254
50000
300000
1000000
Returns: 66242
20
200000
1000
Returns: 8419
200
299999
383
Returns: 299999