No.2168 Two-Headed Hydra Game
タグ : / 解いたユーザー数 8
作問者 : 👑
testestest
Note
The title and tags were edited after the contest ended. The content of the problem itself has not changed.
Problem Statement
We recursively define what it means for a string consisting only of the $3$ kinds of characters (, |, and ) to be a two-headed hydra as follows:
- The empty string is a two-headed hydra.
- For any two-headed hydras $t_0$, $t_1$, and $t_2$, the string obtained by concatenating
(, $t_0$,|, $t_1$,), and $t_2$ in this order is a two-headed hydra.
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 certain characters. What we explain here is the phrasing peculiar to mathematics used when recursively defining things such as subsets of $X$.
For example, using an element $c$ of $X$, non-negative integers $n,m$, and a map $F \colon X^n \times X^m \to X$, one may write the following:
We recursively define a subset $A$ of $X$ as follows:
- $c \in A$.
- For any $(a,t) \in A^n \times X^m$, we have $F(a,t) \in A$.
This is merely an example. Here we used $2$ conditions, but in general the number is not limited to $2$, 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 both of the $2$ 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 both of the following $2$ conditions:
- $c \in B$.
- For any $(a,t) \in B^n \times X^m$, we have $F(a,t) \in B$.
Taking $B = X$ indeed satisfies the above $2$ conditions, so the set of all $B$ satisfying the conditions is non-empty and the intersection is well-defined. It then follows that $A$ is the smallest among the $B$ satisfying the $2$ conditions.
Thus, note that by convention a recursive definition of a subset is not just a 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, using 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 $1$-ary relations on $X$. Specifically,
We recursively define 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 \times X^m$, if every component of $a$ is a good term, then $F(a,t)$ is also a good term.
when a recursive definition of the $1$-ary relation "is a good term" is written like this, it does not mean that the predicate "is a good term" stands for an arbitrary $1$-ary relation satisfying the $2$ 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 both of the following $2$ conditions:
- $c \in B$.
- For any $(a,t) \in B^n \times X^m$, we have $F(a,t) \in B$.
Given the above, the recursive definition of two-headed hydras in this problem is equivalent to the following definition:
We define a string $t$ consisting only of the $3$ kinds of characters
(,|, and)to be a two-headed hydra if, for every set $B$ consisting only of strings made up only of(,|, and), $t \in B$ holds whenever $B$ satisfies both of the following $2$ conditions:
- The empty string is an element of $B$.
- For any elements $t_0$, $t_1$, and $t_2$ of $B$, the string obtained by concatenating
(, $t_0$,|, $t_1$,), and $t_2$ 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 below,
- the recursive definitions of the $1$-ary relations "be an $\mathcal{L}$-term" and "be an $\mathcal{L}$-formula" in [1], etc.
- the recursive definitions of the set $T$ and the $1$-ary relation "be a principal term" in [2], etc.
- the recursive definitions of the sets $B(\alpha,\beta)$ and $\textrm{K}_{\kappa}(\gamma)$ in [3], etc.
actually adopt such phrasing.
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.
The two-headed hydra that is the empty string is called the dead two-headed hydra. A two-headed hydra that is not the dead two-headed hydra is called a living two-headed hydra.
A two-headed hydra $t$ is a gentle two-headed hydra if there exists a two-headed hydra $t'$ such that $t$ is the string obtained by concatenating $t'$ and (|) in this order.
A living two-headed hydra that is not a gentle two-headed hydra is called a ferocious two-headed hydra.
For a two-headed hydra $t$ and a non-negative integer $n$, we recursively define the two-headed hydra $t[n]$ as follows:
- If $t$ is the dead two-headed hydra, then $t[n]$ is the dead two-headed hydra.
- Suppose there exist two-headed hydras $t_0$, $t_1$, and $t_2$ such that $t$ is the string obtained by concatenating
(, $t_0$,|, $t_1$,), and $t_2$ in this order. - If $t_2$ is a living two-headed hydra, then $t[n]$ is the string obtained by concatenating
(, $t_0$,|, $t_1$,), and $t_2[n]$ in this order. - If $t_0$, $t_1$, and $t_2$ are dead two-headed hydras, then $t[n]$ is the dead two-headed hydra.
- Suppose $t_0$ and $t_2$ are dead two-headed hydras and $t_1$ is a living two-headed hydra.
- If $n = 0$, then $t[n]$ is the string obtained by concatenating
(|, $t_1[0]$, and)in this order. - If $n > 0$, then $t[n]$ is the string obtained by concatenating
(|, $t_1[n]$,), and $t[n-1]$ in this order. - Suppose $t_1$ and $t_2$ are dead two-headed hydras and $t_0$ is a living two-headed hydra.
- If $n = 0$, then $t[n]$ is the string obtained by concatenating
(, $t_0[0]$, and|)in this order. - If $n > 0$, then $t[n]$ is the string obtained by concatenating
(, $t_0[n]$,|, $t[n-1]$, and)in this order. - Suppose $t_2$ is a dead two-headed hydra, $t_0$ is a living two-headed hydra, and $t_1$ is a gentle two-headed hydra.
- If $n = 0$, then $t[n]$ is the string obtained by concatenating
(, $t_0[0]$,|(, $t_0$,|, $t_1[0]$, and)(|))in this order. - If $n > 0$, then $t[n]$ is the string obtained by concatenating
(, $t_0[n]$,|, $t[n-1]$, and)in this order. - If $t_2$ is a dead two-headed hydra, $t_0$ is a living two-headed hydra, and $t_1$ is a ferocious two-headed hydra, then $t[n]$ is the string obtained by concatenating
(, $t_0$,|, $t_1[n]$, and)in this order.
Two-Headed-Hydra-Loving Bot is a bot that loves two-headed hydras.
Two-Headed-Hydra-Loving-Bot-Loving Bot is a bot that loves Two-Headed-Hydra-Loving Bot. Of course, the two are different bots.
For distinct living two-headed hydras $t_0$ and $t_1$, the two-headed hydra game with initial values $t_0$ and $t_1$, whose two players are Two-Headed-Hydra-Loving Bot and Two-Headed-Hydra-Loving-Bot-Loving Bot, is defined as follows:
- First, Two-Headed-Hydra-Loving Bot is given the two-headed hydra $t_0$, and Two-Headed-Hydra-Loving-Bot-Loving Bot is given the two-headed hydra $t_1$.
- Next, the two players, starting with Two-Headed-Hydra-Loving Bot, alternately perform the following operation until their two-headed hydras coincide:
- Choose $1$ non-negative integer $n$, and replace one's own two-headed hydra $t$ with $t[n]$.
If this game ends after a finite number of operations, the player who performed the last operation wins.
Living two-headed hydras $T_0$ and $T_1$ are given as input.
In the two-headed hydra game with initial values $T_0$ and $T_1$, when the two bots choose their best moves so as to aim for their own victory and avoid the opponent's victory, determine whether the game is decided within a finite number of operations and, if it is decided, which one wins.
Input
The input is given from standard input in the following format:
$T_0$ $T_1$
The two-headed hydra $T_0$ is given on line $1$, and the two-headed hydra $T_1$ is given on line $2$.
Constraints
The input satisfies the following constraints:
- $T_0$ is a living two-headed hydra whose length as a string is at most $30$
- $T_1$ is a living two-headed hydra whose length as a string is at most $30$
- $T_0$ and $T_1$ are distinct
Output
In the two-headed hydra game with initial values $T_0$ and $T_1$, when the two bots choose their best moves so as to aim for their own victory and avoid the opponent's victory,
- if the game is not decided within a finite number of operations, print
-1 - if Two-Headed-Hydra-Loving Bot, who moves first, wins, print
0 - if Two-Headed-Hydra-Loving-Bot-Loving Bot, who moves second, wins, print
1
Print as described above.
Print a newline at the end.
Sample
Sample 1
Input
(|)(|) (|)
Output
0
First, the two-headed hydra of Two-Headed-Hydra-Loving Bot is initialized to (|)(|), and the two-headed hydra of Two-Headed-Hydra-Loving-Bot-Loving Bot is initialized to (|).
Next, if Two-Headed-Hydra-Loving Bot chooses $n = 0$, the two-headed hydra of Two-Headed-Hydra-Loving Bot is replaced with (|). This coincides with the two-headed hydra of Two-Headed-Hydra-Loving-Bot-Loving Bot.
Therefore, Two-Headed-Hydra-Loving Bot has a winning strategy.
Sample 2
Input
(|) (|)(|)
Output
1
First, the two-headed hydra of Two-Headed-Hydra-Loving Bot is initialized to (|), and the two-headed hydra of Two-Headed-Hydra-Loving-Bot-Loving Bot is initialized to (|)(|).
Next, Two-Headed-Hydra-Loving Bot chooses a non-negative integer $n$, and its two-headed hydra $t$ is replaced with $t[n]$, which is the dead two-headed hydra regardless of the choice of $n$. In particular, it differs from the two-headed hydra of Two-Headed-Hydra-Loving-Bot-Loving Bot.
Then, if Two-Headed-Hydra-Loving-Bot-Loving Bot chooses $n=0$, its two-headed hydra $t$ is replaced with $t[0]$, which is the living two-headed hydra (|). In particular, it differs from the two-headed hydra of Two-Headed-Hydra-Loving Bot.
Now Two-Headed-Hydra-Loving Bot chooses a non-negative integer $n$, and its two-headed hydra $t$ is replaced with $t[n]$; since $t$ is the dead two-headed hydra, $t[n]$ is also the dead two-headed hydra regardless of the choice of $n$. In particular, it differs from the two-headed hydra of Two-Headed-Hydra-Loving-Bot-Loving Bot.
Once again, if Two-Headed-Hydra-Loving-Bot-Loving Bot chooses $n=0$, its two-headed hydra $t$ is replaced with $t[0]$, which is the dead two-headed hydra and coincides with the two-headed hydra of Two-Headed-Hydra-Loving Bot.
Therefore, Two-Headed-Hydra-Loving-Bot-Loving Bot has a winning strategy.
Sample 3
Input
(|(|)) (|)(|)(|)
Output
0
Sample 4
Input
(|)(|)(|) (|(|))
Output
1
Sample 5
Input
((|)|) (|(|(|)))
Output
0
Sample 6
Input
(|(|(|))) ((|)|)
Output
1
Sample 7
Input
((|)(|)|) ((|)|((|)|))
Output
0
Sample 8
Input
((|)|((|)|)) ((|)(|)|)
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。