SquareLanguage
SRM 238 · 2005-04-14 · by AdminBrett
SRM 238 · 2005-04-14 · by AdminBrett · Math, String Manipulation
Problem Statement
Problem Statement
The problem statement contains superscripts that are viewable in the applet.
Let S be a set of distinct strings. We form the new set S2 by collecting all distinct strings of the form xy, where the prefix x is in S, and the suffix y is in S as well. Suppose S is defined as follows:
Let S be a set of distinct strings. We form the new set S2 by collecting all distinct strings of the form xy, where the prefix x is in S, and the suffix y is in S as well. Suppose S is defined as follows:
S = {ai bj ck dm | la <= i <= ua, lb <= j <= ub, lc <= k <= uc, ld <= m <= ud }
Here ai denotes the letter 'a' repeated i times. For example, a3 b2 c0 d1 = aaabbdYou will be given l_ and u_ as the first and second elements of _bounds respectively (here _ denotes a, b, c, or d). Return the number of strings in S2.
Notes
- The set notation T = { x | prop } means that T contains all elements x such that prop is true.
Constraints
- abounds, bbounds, cbounds and dbounds will each contain exactly 2 elements.
- In abounds, bbounds, cbounds and dbounds element 0 will not be greater than element 1.
- In abounds, bbounds, cbounds and dbounds element 0 will be between 0 and 100 inclusive.
- In abounds, bbounds, cbounds and dbounds element 1 will be between 0 and 100 inclusive.
Examples
0)
{0,100}
{0,100}
{0,100}
{0,100}
Returns: 10828525844240801
1)
{0,10}
{0,10}
{0,10}
{0,10}
Returns: 213826481
2)
{1,10}
{1,10}
{1,10}
{1,10}
Returns: 100000000
3)
{0,2}
{0,2}
{0,2}
{0,2}
Returns: 6129
4)
{0,1}
{0,1}
{0,1}
{0,1}
Returns: 224
8)
{0,100}
{0,0}
{0,0}
{0,0}
Returns: 201
Here there are 201 possible strings. Each one is distinguished by the number of a's it contains.
9)
{0,1}
{0,1}
{0,0}
{0,0}
Returns: 12
The 12 strings in S2 are "", "a", "b", "aa", "ab", "ba", "bb", "bab", "aab", "abb", "aba", and "abab".
10)
{1,100}
{10,90}
{20,80}
{30,70}
Returns: 410390615610000
Here there is no danger of duplicates.
18)
{0,2}
{0,2}
{0,0}
{0,0}
Returns: 57
The 12 strings in S2 are "", "a", "b", "aa", "ab", "ba", "bb", "bab", "aab", "abb", "aba", and "abab".
Submissions are judged against all 54 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SquareLanguage with a public method long long howMany(vector<int> abounds, vector<int> bbounds, vector<int> cbounds, vector<int> dbounds) · 54 test cases · 2 s / 256 MB per case