RaiseThisBarn
SRM 593 · 2013-06-25 · by tozangezan
SRM 593 · 2013-06-25 · by tozangezan · Brute Force, String Manipulation
Problem Statement
Problem Statement
The pony Applejack is going to raise a new barn.
The barn will consist of N sections in a row.
Some of the sections will be empty, others will contain a single cow each.
You are given a String str with N characters.
This string describes the desired layout of the barn:
the character 'c' represents a section with a cow, and the character '.' represents an empty section.
After she raises the barn, Applejack will build a wall that will divide the barn into two separate parts: one containing the first k sections and the other containing the last N-k sections, for some integer k. Each part must contain at least one section. (I.e., k must be between 1 and N-1, inclusive.) Additionally, Applejack wants both parts to contain exactly the same number of cows.
Return the number of possible positions for the wall. In other words, return the number of choices for the integer k such that all the conditions above are satisfied.
After she raises the barn, Applejack will build a wall that will divide the barn into two separate parts: one containing the first k sections and the other containing the last N-k sections, for some integer k. Each part must contain at least one section. (I.e., k must be between 1 and N-1, inclusive.) Additionally, Applejack wants both parts to contain exactly the same number of cows.
Return the number of possible positions for the wall. In other words, return the number of choices for the integer k such that all the conditions above are satisfied.
Constraints
- str will contain between 2 and 50 characters, inclusive.
- Each character in str will be 'c' or '.'.
Examples
0)
"cc..c.c" Returns: 3
Applejack can choose k=2, k=3, or k=4. The three corresponding solutions are shown below, with '|' representing the wall between the two parts. cc|..c.c cc.|.c.c cc..|c.c
1)
"c....c....c" Returns: 0
There is an odd number of cows. It is impossible to divide them into two equal halves.
2)
"............" Returns: 11
This is a barn with 12 empty sections. It can be divided in 11 different ways: into 1+11 sections, 2+10 sections, ..., or 11+1 sections.
3)
".c.c...c..ccc.c..c.c.cc..ccc" Returns: 3
4)
".." Returns: 1
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RaiseThisBarn with a public method int calc(string str) · 87 test cases · 2 s / 256 MB per case