PresentationComp
SRM 221 · 2004-12-01 · by AdminBrett
SRM 221 · 2004-12-01 · by AdminBrett · Encryption/Compression, Math, String Manipulation
Problem Statement
Problem Statement
In algebra, a presentation is a convenient way to describe a set. The presentation includes what the atomic elements of the set are, and what relations are used to simplify strings of atoms. These atoms are usually called generators. In this problem we will be looking at a set whose generators are x and y. You will be given a String expression consisting of x's and y's. The simplifying rules are:
- 1) Any occurrence of yyyyyy can be deleted from the string.
- 2) Any occurrence of xxxxxxxx can be deleted from the string.
- 3) Any occurrence of xy can be replaced by yyyyyx.
Constraints
- expression will contain between 1 and 50 characters inclusive.
- Each character in expression will be x or y.
Examples
0)
"xyxyxyxyxyx" Returns: "xxxxxyx"
1)
"xxxx" Returns: "xxxx"
2)
"yyyy" Returns: "yyyy"
3)
"xyxyxyxyxyxyxyxyxxyyxyxyxyxxyyxyxyx" Returns: "xyx"
4)
"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy" Returns: "y"
6)
"xxxxxxxxyyyyyy" Returns: ""
Simplifies greatly.
7)
"xy" Returns: "xy"
Doesn't get much simpler.
8)
"yyxx" Returns: "xxyy"
Use the one that comes first alphabetically.
Submissions are judged against all 174 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PresentationComp with a public method string simplify(string expression) · 174 test cases · 2 s / 256 MB per case