TopCoder problem "PrintScheduler" used in SRM 238 (Division I Level One , Division II Level Two)



Problem Statement

    The output of a multithreaded system can be quite garbled, due to the interleaved execution that occurs. In this problem, we will model such a situation. Each thread's output will be described by a string. For example, the string "AB" would mean that after 1 time unit running, the thread would print an 'A'. After another time unit it would print a 'B'. After a third time unit, it would print an 'A' (wraps back to the beginning). You will be given a String[] describing the threads to be run. You will also be given a String[] containing the time slices each thread is given. Each element of slices will have the form "Thread# Time". Thread# is a 0-based index into threads. Time is how many units of time the thread in question will execute for. The elements of slices occur in the order they will be run. If a thread is executed, and then executed again at a later point, it starts where it left off (see examples for further clarification).



You will return a String containing the output in the order it occurred. For example, if 
  threads = {"AB","CD"}
  slices = {"0 1","1 1","0 1","1 2"}
Then you would return "ACBDC".
 

Definition

    
Class:PrintScheduler
Method:getOutput
Parameters:String[], String[]
Returns:String
Method signature:String getOutput(String[] threads, String[] slices)
(be sure your method is public)
    
 

Constraints

-threads will contain between 1 and 50 elements inclusive.
-Each element of threads will contain between 1 and 50 characters inclusive.
-Each character in each element of threads will be a capital letter.
-slices will contain between 1 and 50 elements inclusive.
-Each element of slices will have the form "Thread# Time".

Thread# will be an integer, without extra leading zeros, between 0 and k-1 inclusive, where k is the number of elements in threads.

Time will be an integer, without leading zeros, between 1 and 50 inclusive.
 

Examples

0)
    
{"AB","CD"}
{"0 1","1 1","0 1","1 2"} 
Returns: "ACBDC"
From the problem statement. The output occurs as follows:
  Thread 0 - Runs for 1 unit  - Outputs "A"
  Thread 1 - Runs for 1 unit  - Outputs "C"
  Thread 0 - Runs for 1 unit  - Outputs "B"
  Thread 1 - Runs for 2 units - Outputs "DC"
1)
    
{"ABCDE"}
{"0 20","0 21"}
Returns: "ABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEA"
2 long time slices.
2)
    
{"A","B"}
{"1 10","0 1","1 10","0 2"}
Returns: "BBBBBBBBBBABBBBBBBBBBAA"
3)
    
{"A"}
{"0 1"}
Returns: "A"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4504

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6537&pm=4504

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Simulation