Procrastination
SRM 672 · 2015-08-31 · by Zlobober
Problem Statement
You are working in the Huge Software Company. The company is so huge that it has an infinite number of employees. Employee number 1 is reserved for the Big Boss and Legendary Founder of the company, Mr. Z. Ordinary employees are numbered using positive integers, starting from 2.
At the beginning of the day each employee is assigned a task they should accomplish: for each x from 2 to infinity, employee number x is assigned task number x. During the day some pairs of employees will swap the tasks they were assigned. The swapping follows a precise schedule that is described below.
The working day in the Huge Software Company has infinitely many hours. The hours are numbered using positive integers, starting from 1. During hour 1 there are no swaps at all. During each of the following hours there are infinitely many swaps. These look as follows:
- During hour 2 we have the following swaps: workers 4 and 5 swap their tasks, workers 6 and 7 swap their tasks, workers 8 and 9 swap their tasks, and so on.
- During hour 3 we have the following swaps: workers 6 and 7 swap their tasks, workers 9 and 10 swap their tasks, workers 12 and 13 swap their tasks, and so on.
- ...
- Formally, for each h greater than or equal to 2, during hour h we look at all workers that have numbers divisible by h and strictly greater than h. Each of these workers will swap the task they currently have with the worker with a number one larger than their own.
It can be shown that for each employee there is a finite number of hours after which the employee will never swap their current task with anyone. It can also be shown that for each task there is a finite number of hours after which the task will remain with the current employee forever.
You are given a
Constraints
- n will be between 2 and 10^10, inclusive.
3 Returns: 3
Employee 3 is never involved in any swaps: neither with employee 2, nor with employee 4.
8 Returns: 11
Task 8 starts assigned to employee 8. During hour 2 this employee swaps it for another task with employee 9. During hour 3 employee 9 gives this task to employee 10. Finally, during hour 5 employee 10 gives this task to employee 11 where it will stay forever.
20 Returns: 20
Task 20 goes from employee 20 to employee 21 (during hour 2), then to employee 22 (during hour 3), then back to employee 21 (during hour 7), and finally back to employee 20 (during hour 10). This is where it then remains forever.
196248 Returns: 196259
5587021440 Returns: 5587021440
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Procrastination with a public method long long findFinalAssignee(long long n) · 55 test cases · 2 s / 256 MB per case