BearCries
SRM 671 · 2015-08-31 · by Errichto
Problem Statement
Limak is a polar bear who often chats online with his friends. Nowadays, bears often use emoticons to express their feelings. In this problem we consider one particular emoticon: the crying emoticon.
A crying emoticon consists of an arbitrary positive number of underscores between two semicolons. Hence, the shortest possible crying emoticon is ";_;" (quotes for clarity). The strings ";__;" and ";_____________;" are also valid crying emoticons.
Today Limak is sad, so he sent his friend a sequence of crying emoticons. However, due to a network malfunction all those emoticons got mixed together into a single string.
You are given a
Let X be the number of ways in which one can divide the given message into emoticons. Compute and return the value (X modulo 1,000,000,007).
Constraints
- message will contain between 1 and 200 characters, inclusive.
- Each character in message will be either semicolon or underscore.
";_;;_____;" Returns: 2
There are two ways to divide this string into two crying emoticons. One looks as follows: ;_; ;_____; and the other looks like this: ;_ ; ; _____;
";;;___;;;" Returns: 36
This message consists of 3 semicolons, 3 underscores and 3 semicolons again. Clearly, we have to divide this message into exactly three crying emoticons, each with a single underscore. There are 36 different ways to do so.
"_;__;" Returns: 0
As this message begins with an underscore, it clearly cannot be divided into one or more crying emoticons: each crying emoticon starts with a semicolon.
";_____________________________________;" Returns: 1
";__;____;" Returns: 0
"_" Returns: 0
fake
"_" Returns: 0
fake
Submissions are judged against all 70 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearCries with a public method int count(string message) · 70 test cases · 2 s / 256 MB per case