No.2539 Slime Game
Note
The execution time limit for this problem is 1000[ms].
Problem Statement
Here, a string consisting only of the $2$ kinds of characters ( and ) is called a slime.
A slime that is the empty string is called a dead slime. A slime that is not a dead slime is called a living slime.
We define recursively what it means for a slime to be a perfect slime, as follows:
- A dead slime is a perfect slime.
- For any perfect slimes $s_0$ and $s_1$, the slime that is the string $s_0 s_1$ obtained by concatenating $s_0$ and $s_1$ in this order is a perfect slime.
- For any perfect slime $s$, the slime that is the string
($s$)obtained by concatenating(, $s$, and)in this order is a perfect slime.
Below is an explanation for those who are not familiar with recursive definitions of sets and the like. (Click to open)
Let $X$ be a set. For example, $X$ may be the set of strings consisting only of specific characters. What we explain here is the phrasing peculiar to mathematics used when recursively defining subsets of $X$ and the like.
For example, using an element $c$ of $X$, non-negative integers $n_0,m_0,n_1,m_1$, and maps $F_0 \colon X^{n_0} \times X^{m_0} \to X$ and $F_1 \colon X^{n_1} \times X^{m_1} \to X$, one may write the following:
We define the subset $A$ of $X$ recursively as follows:
- $c \in A$.
- For any $(a,t) \in A^{n_0} \times X^{m_0}$, $F_0(a,t) \in A$.
- For any $(a,t) \in A^{n_1} \times X^{m_1}$, $F_1(a,t) \in A$.
This is merely an example. We used $3$ conditions here, but in general there need not be exactly $3$, and relations may be used instead of maps. The general formulation of recursive definitions[1] 6.1.1 Definition is quite abstract, so here we consider only the examples needed to solve this problem.
The important point is that this definition does not mean that $A$ is simply an arbitrary subset of $X$ satisfying all $3$ conditions; rather, it stands for the following definition:See [1] 6.1.2 Definition and the paragraph immediately after it
We define the subset $A$ of $X$ as the intersection of all subsets $B$ of $X$ satisfying all of the following $3$ conditions:
- $c \in B$.
- For any $(a,t) \in B^{n_0} \times X^{m_0}$, $F_0(a,t) \in B$.
- For any $(a,t) \in B^{n_1} \times X^{m_1}$, $F_1(a,t) \in B$.
Taking $B = X$ does satisfy the above $3$ conditions, so the set of all $B$ satisfying the conditions is non-empty and the intersection is well-defined. It then follows as a consequence that $A$ is the smallest among the $B$ satisfying the $3$ conditions.
Note that, in this way, a recursive definition of a subset is by convention not a mere list of conditions but also implies minimality. However, this convention applies only to recursive definitions. An ordinary definition of course does not imply minimality, and in the first place, self-reference like that of a recursive definition in an ordinary definition usually results in circular reasoning, and the definition breaks down.
Now, since a $1$-ary relation on $X$ is equivalent to a subset of $X$, the same rule applies to recursive definitions of a $1$-ary relation on $X$. Specifically, suppose we write a recursive definition of the $1$-ary relation "is a good term" as follows:
We define recursively what it means for an element of $X$ to be a good term, as follows:
- $c$ is a good term.
- For any $(a,t) \in X^{n_0} \times X^{m_0}$, if every component of $a$ is a good term, then $F_0(a,t)$ is also a good term.
- For any $(a,t) \in X^{n_1} \times X^{m_1}$, if every component of $a$ is a good term, then $F_1(a,t)$ is also a good term.
This does not mean that the predicate "is a good term" stands for an arbitrary $1$-ary relation satisfying the $3$ conditions. The above definition is equivalent to the following definition:
We define an element $x$ of $X$ to be a good term if $x \in B$ holds for every subset $B$ of $X$ satisfying all of the following $3$ conditions:
- $c \in B$.
- For any $(a,t) \in B^{n_0} \times X^{m_0}$, $F_0(a,t) \in B$.
- For any $(a,t) \in B^{n_1} \times X^{m_1}$, $F_1(a,t) \in B$.
Given the above, the recursive definition of a perfect slime in this problem is equivalent to the following definition:
We define a slime $s$ to be a perfect slime if, for every set $B$ consisting only of slimes, $s \in B$ holds whenever $B$ satisfies all of the following $3$ conditions:
- The empty string is an element of $B$.
- For any elements $t_0$ and $t_1$ of $B$, the string obtained by concatenating $t_0$ and $t_1$ in this order is an element of $B$.
- For any element $t$ of $B$, the string obtained by concatenating
(, $t$, and)in this order is an element of $B$.
This is considerably more complicated than the original phrasing. To avoid such complicated phrasing, mathematics defines and adopts the concise phrasing introduced here.
For example, in the references listed later, namely
- the recursive definitions of the $1$-ary relations "be an $\mathcal{L}$-term" and "be an $\mathcal{L}$-formula" in [1], and so on
- the recursive definitions of the set $T$ and the $1$-ary relation "be a principal term" in [2], and so on
- the recursive definitions of the sets $B(\alpha,\beta)$ and $\textrm{K}_{\kappa}(\gamma)$ in [3], and so on
such phrasing is actually adopted.
References
- W. Pohlers, "Proof Theory - The first step into impredicativity", Springer, 2010.
- W. Buchholz, "A New System of Proof-Theoretic Ordinal Functions", Annals of Pure and Applied Logic 32 (1986), pp. 195--207.
- M. Rathjen, "Ordinal Notations Based on a Weakly Mahlo Cardinal", Archive for Mathematical Logic 29 (1990), pp. 249--263.
Attacking a slime $s$ means replacing $s$ with the slime $\Sigma s$, recursively defined as follows:
- Suppose there exist a slime $t$ and a perfect slime $u$ such that $s$ is the string $t$
($u$)obtained by concatenating $t$,(, $u$, and)in this order. - If $u$ is a dead slime, then $\Sigma s = t$.
- If $u$ is a living slime, let $v$ be the slime that is the string $t$
($\Sigma u$)($\Sigma u$)obtained by concatenating $t$,(, $\Sigma u$,)(, $\Sigma u$, and)in this order; then $\Sigma s = \Sigma v$. - Otherwise, $\Sigma s$ is a dead slime.
It is known that the pair of $t$ and $u$ in branch 1 above is unique, and it is guaranteed that $\Sigma s$ is uniquely determined.
We say that $s$ is defeatable if attacking $s$ $10^{18}$ times turns $s$ into a dead slime.
If $s$ is defeatable, the minimum number of attacks required to replace $s$ with a dead slime is called the HP of $s$. For example, if $s$ is a dead slime from the beginning, the HP of $s$ is $0$.
A slime $S$ is given as input.
Determine whether $S$ is defeatable, and if it is, find its HP.
Input
The input is given from standard input in the following format:
$S$
Constraints
The input satisfies the following constraints:
- $S$ is a slime whose length as a string is at least $1$ and at most $10^5$
Output
If $S$ is not defeatable, print INFTY; if it is defeatable, print its HP on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
(
As in this case, the numbers of ( and ) may differ.
Output
1
Attacking ( replaces it with a dead slime.
Sample 2
Input
()()
Output
2
Attacking ()() replaces it with the living slime ().
Attacking () replaces it with a dead slime.
Sample 3
Input
(()
Output
2
Attacking (() replaces it with the living slime (. Note that it is not replaced with ().
Attacking ( replaces it with a dead slime.
Sample 4
Input
(())
Output
2
Attacking (()) replaces it with the living slime ().
Attacking () replaces it with a dead slime.
Sample 5
Input
(((((((((())))))))))
Output
INFTY
(((((((((()))))))))) is not defeatable, so print INFTY.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。