Gym
SRM 817 · 2021-10-21 · by misof
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.
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.
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
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.
Submissions are judged against all 66 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Gym with a public method int calculateProfit(int M, int N, int T) · 66 test cases · 2 s / 256 MB per case