|You have written a complicated multi-threaded program, and you would like to analyze its expected runtime.
The program consists of n threads in a specific order, indexed from 0 to n-1. Each thread has a task to execute which is divided into up to 10 subtasks. Each subtask requires one time slice to process, and they must be processed in order. In every thread (except the first), one of the subtasks will be a special "synchronization" subtask; the thread may not process this subtask until all the threads with lower indices have finished. The thread's task is described as a String with a character for each subtask. A normal subtask is denoted by a '.'; the "synchronization" subtask is denoted by 'S'.
The processor executes your program in a simple way. For each time slice it picks a thread uniformly at random and allows it to process one subtask. If the chosen thread has already finished, the unfinished thread with the lowest index is picked instead. However, if the chosen thread is blocked on a "synchronization" subtask, that time slice is wasted. (Yes, this is a silly way to implement multithreading!)
Return the expected (average) number of time slices the entire program will take to execute.
|-||The returned value must be accurate to within a relative or absolute value of 1E-9.|
|-||threads will contain between 1 and 10 elements, inclusive.|
|-||Each element of threads will contain between 1 and 10 characters, inclusive.|
|-||Each element of threads will contain only the characters '.' and 'S'.|
|-||Each element of threads, except the first, will have exactly one 'S'.|
|-||The first element of threads will not contain an uppercase 'S'.|