MAR - Markov Algorithm
Markov schemes are well known field of study in theory of algorithms. Let's define some slightly simplified schemes. We have some character set (alphabet), and a string composed of these symbols. Besides, we have rules of replacement, and each rule specifies the substring to be replaced and the replacement string. The replacement string can be empty. The order of rules is fixed. Everything functions as follows. Rules are looked through in input order. The first rule which can be applied, is applied exactly once (the given replacement which is described by the rule is carried out), and then the operation cycle repeats (the list is looked through anew). If there are many substrings in the line which satisfy a given rule then only the first (i.e., the leftmost) will be replaced. The process comes to an end if after the last rule application the line has not changed. During the process of replacements the length of the initial string can change, increasing or decreasing.
Let’s consider the string ababaab
and the set of rules
As a result of the application of rules the initial string will be transformed into “cac”. The following intermediate results will appear: ababaab, cabaab, ccaab, ccac, abac, cac.
That’s all. And now some tasks.
Task 1: The initial non-empty string was obtained from an ordinary arithmetic formula by the deletion of every symbol except brackets. You are to write the set of rules which transforms this string into the string "RIGHT" or "WRONG" depending on the correctness of brackets positions, following rules of bracket use in arithmetical expressions. For example, the string ()((())()) must be replaced by the string RIGHT, while the string (() must be replaced by the string WRONG with the same replacement rules.
Task 2: The initial string represents an arbitrary string of the following type [integer1]+[integer2]=?, where [integer1] and [integer2] are decimal representation of some positive integers. You are to write a set of rules which translates the initial string into a string of the following type: [integer1]+[integer2]=[sum], where [sum] is the decimal representation of the sum of two numbers integer1 and integer2. For example, the string 2+2=? must be replaced by 2+2=4, and the string 25+76=? must be replaced by 25+76=101. The integers can be up to 100 digits in decimal notation.
Task 3: You are given a string which consists of uppercase letters (A-Z), and ends with the "?" sign. You are to output this string in reverse order without the “?” sign. For example, the string ABBCD? must be transformed into DCBBA
Task 4: You are given a binary integer which consists of 0s and 1s. You are to write it as a string of letters “z”, and the total number of such letters must be equal to the given binary number. For example, 110 must be translated by the algorithm into “zzzzzz”
Task 5: You are given a string which consists of uppercase letters (A-Z), and ends with the "?" sign. You are to output this string in non-descending order without the “?” sign. After applying the rules to DFAAS?, the string should look like this: AADFS
Task 6: You are given two decimal positive integers separated by the "_" symbol and followed by "=?", for example 30_42=?. You are to find and output the value of the greatest common divisor for this pair. For example for 30_42=? it’ll be 6.
Note: The limit on the increase of the string during the work of the algorithm is 100000 symbols.
There is no input data for this problem.
You should output your solutions to every task one by one. If you don’t want to solve some particular task just output 0, otherwise output the length of your solution N. Then output exactly N lines abc->def, where abc is the substring for replacement, and def is the substring by which it will be replaced.
For each correctly solved task you gain 1 point and additionally 1/N bonus points, where N is the length of the proposed solution.
Output: 0 0 0 5 a->b b->c d->v g->l l->a 0 0 Score: In this case (if the set of rules leads to a correct answer)
you’ll get 1 + 0.2 = 1.2 points for the 4-th task.
The number in task 6 is larger than 9999
The integers in task 6 aren't very small, as my solution using [snip] made the judge time out (internal error). It would be nice to know the maximum value of those integers. I don't see the point of making users guess.
Hagen von Eitzen:
Have somebody founded algorithm for first task smaller then 8 commands?
What happens if the limit of 100000 on the increase of the string is reached?
In task 6, are we supposed to leave just the GCD (e.g. "6") or the whole equation as in task 3 (e.g. "30_42=6")?
|Added by:||Roman Sol|
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PERL6 PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST VB.NET WHITESPACE|