CowsMooing | Topcoder Archive

Problem Statement

Farmer Brus noticed that his N cows are mooing according to their own patterns. You are given a String[] patterns. The i-th cow's mooing pattern is described by patterns[i]. The cow reads its pattern from left to right. When it reads character 'M', it moos for one second, and when it reads character '-', it becomes quiet for one second. If it reaches the end of its pattern, it will repeat reading from the beginning and continue infinitely. More formally, during the time interval between t seconds from the beginning and t+1 seconds from the beginning, the i-th cow reads the character (t modulo length(patterns[i])) of patterns[i]. The i-th cow moos if and only if this character is 'M'.

Let's define loudness as the number of mooing cows. Farmer Brus wants to calculate the distribution of loudness during the first 50! (= 1 x 2 x ... x 49 x 50) seconds. Return a int[] containing exactly N+1 elements. Let T[i] be the total number of seconds in the considered range when the loudness was exactly i. For all i, the i-th element of the return value must be the value (T[i] modulo 10,007).

Definition

Class:: CowsMooing
Method:: getDistribution
Parameters:: String[]
Returns:: int[]
Method signature:: int[] getDistribution(String[] patterns)
(be sure your method is public)

Constraints

patterns will contain between 1 and 30 elements, inclusive.
Each element of patterns will contain between 1 and 50 characters, inclusive.
Each character in each element of patterns will be either 'M' or '-'.

Examples

```
{"M"}
```
```
Returns: {0, 3235 }
```
The only cow is always mooing. The return value should be {0, 50! mod 10,007}.
```
{"M--M-",
 "-M-M-"}
```
```
Returns: {1294, 1294, 647 }
```
Cow 0 will be mooing during the intervals (0,1), (3,4), (5,6), (8,9), (10,11), (13,14), ... and so on. Cow 1 will be mooing during the intervals (1,2), (3,4), (6,7), (8,9), (11,12), (13,14), ... and so on.

{"M--",
 "-M--"}

Returns: {6621, 514, 6107 }

{"MM-M---M-MM--",
 "-MM-MMM----M-M-",
 "MM-",
 "M--M-M--"}

Returns: {7907, 7504, 964, 9034, 7847 }

{"-",
 "-M",
 "-MM",
 "-M--",
 "--M--",
 "M---MM",
 "MM-MM--",
 "M-M--M--",
 "M-M-MM-M-",
 "-MMMM-M-M-",
 "M-M-M-M-MMM",
 "--MMM--M--MM",
 "M--MM--MMM-M-",
 "M-MM----MM----",
 "MM----M-MMMM--M",
 "-MMMMM--M-M--M-M",
 "----M-M----MMMMMM",
 "MM-----M-MMM-MMMMM",
 "--M-MMMMMM-MMM-M--M",
 "M-M--M--M-MMM--MM---",
 "--MMMM--MM-MMM-M----M",
 "-MMM-M-MM-MMM-M-M-----",
 "-M-MMMM-MMMM--M--M--M--",
 "-M--MMM--MM---MMMM---MMM",
 "MMMM-MMMMM-M-MMMM-MM--M-M",
 "MMM-MMM-MM--M----M----MM-M",
 "MM---M-MMMMMMM----MM----MM-",
 "M----MMMMMMM-MM--MMM---M----",
 "-M-MMM-MMMM-MM--M-MMM---M----",
 "M--M-M-MM-MMM--M---MMMMMM-M-MM"}

Returns: {0, 0, 0, 9523, 1842, 4448, 752, 9392, 9394, 7124, 193, 2222, 1873, 1875, 5758, 5429, 1847, 9481, 7496, 108, 7880, 4988, 2656, 4783, 4261, 9987, 0, 0, 0, 0, 0 }

{
"MMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM"}

Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3235 }

A lot of very loud cows.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.