CowsMooing

TCO12 Round 3A · 2012-03-27 · by rng_58

TCO12 Round 3A · 2012-03-27 · by rng_58 · Brute Force, Dynamic Programming, Math

Show categories

Class Name: CowsMooing

Return Type: int[]

Method Name: getDistribution

Arg Types: (vector<string>)

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).

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 }

88)

{
"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.

Submissions are judged against all 262 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CowsMooing with a public method vector<int> getDistribution(vector<string> patterns) · 262 test cases · 2 s / 256 MB per case