Shoelaces
TCCC '03 Semifinals 3 · 2003-04-04 · by vorthys
Problem Statement
Concurrency can be simulated on a single processor using the technique of time-slicing, giving each process a chance to run for some small, fixed interval before switching to the next process. For example, two processes might take turns executing for 10 milliseconds each until both have finished. However, switching between processes is expensive, so it is sometimes desirable to allow a process to execute more than one time slice in a row. On the other hand, to preserve the illusion of parallel execution, it is desirable that no process have to wait too long before getting a chance to run. One way to balance these conflicting desires is to set a limit K on the number of time slices a process might wait between turns. More precisely, no process that still needs more time slices will ever wait more than K time slices before getting a chance to run.
Consider two processes, A and B, that both need to run for N time slices. Given N and K, your task is to determine how many ways there are to schedule A and B such that A gets the first time slice and B gets the last time slice. For example, if N=3 and K=3, there are six possible schedules:
AAABBB
AABABB
AABBAB
ABAABB
ABABAB
ABBAAB
If K is reduced to 2, then the AAABBB schedule is eliminated, leaving five possible schedules.
Your task is to write a method that takes two integers, N (the number of time slices needed by each process) and K (the maximum number of time slices an unfinished process is willing to wait),
and returns the number of possible schedules as a
Constraints
- N is between 1 and 30, inclusive.
- K is between 1 and 30, inclusive.
3 3 Returns: 6
3 2 Returns: 5
The example above.
5 3 Returns: 59
4 2 Returns: 12
The twelve possible schedules are AABAABBB ABAABABB ABBAABAB AABABABB ABAABBAB ABBABAAB AABABBAB ABABAABB AABBAABB ABABABAB AABBABAB ABABBAAB Notice in the first schedule (AABAABBB) that process B runs for three time slices in a row even though K=2. This is legal because process A has already finished.
15 1 Returns: 1
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TimeSlicing with a public method long long howMany(int N, int K) · 38 test cases · 2 s / 256 MB per case