問題一覧 > 教育的問題

No.2397 Powers of ω

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : 👑 p-adic / テスター : testestest googol_S0
お気に入りにしたユーザー ProblemId : 8859 / 自分の提出
問題文最終更新日: 2023-03-05 22:37:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 399 (順位表) の他の問題:

Problem Statement

This problem is based on ordinal arithmetic. Stating the usual definition of ordinal arithmetic would require explaining the complicated definition of ordinals, so here we instead introduce a set operation that extends ordinal arithmetic, using only the language of general sets.

 

For sets $X, Y$ and a non-negative integer $n$, we define the set $X + \omega^Y \times n$ recursively as follows:

$\displaystyle X + \omega^Y \times n = \left\{ \begin{array}{ll} X & (n = 0) \\ X \cup \{X\} & (n = 1 \land Y = \{\}) \\ \bigcup_{y \in Y} \bigcup_{m = 0}^{\infty} (X + \omega^y \times m) & (n = 1 \land Y \neq \{\}) \\ (X + \omega^Y \times (n-1)) + \omega^Y \times 1 & (n > 1) \end{array} \right. $

Note that in modern set theory, sets are formalized so that all of their elements are sets. Therefore each element $y$ of $Y$ is also a set, and $X + \omega^y \times m$ in the above formula is well-formed.

With respect to the operation defined in this way, $\{\} + \omega^{\{\{\}\}} \times 1$ is written as $\omega$ in the context of ordinals, and for ordinals $\alpha, \beta$ and a positive integer $n$, $\alpha + \omega^{\beta} \times n$ under this formulation coincides exactly with that under the usual ordinal arithmetic. It is known that every ordinal can be expressed as a finite sum of $0$ or more powers of $\omega$ with respect to the usual ordinal arithmetic. In particular, it is known that using the representation called the Cantor normal form with base $\omega$, the $\in$ relation between ordinals can be determined by lexicographic order. Note, however, that the definition of the lexicographic order on Cantor normal forms itself uses the $\in$ relation (of the ordinals appearing in the exponents).

 

For a positive integer $n$, let $(n_0,n_1)$ denote the unique pair of non-negative integers $(a,b)$ satisfying $n = (2a+1)2^b$.

For a non-negative integer $n$, we define the set $f(n)$ by the following recurrence:

$\displaystyle f(n) = \left\{ \begin{array}{ll} \displaystyle \{\} &\displaystyle (n = 0) \\ \displaystyle f(n_0) + \omega^{f(n_1)} \times 1 &\displaystyle (n \neq 0) \end{array} \right. $

Calculation examples: (click to expand)

 

For example, $f(0),f(1),f(3)$ can be computed as

$\displaystyle \begin{array}{rcl} \displaystyle f(0) &\displaystyle = &\displaystyle \{\} \\ \displaystyle f(1) &\displaystyle = &\displaystyle f((2 \times 0 + 1)2^0) = f(0) + \omega^{f(0)} \times 1 = \{\} + \omega^{\{\}} \times 1 = \{\} \cup \{\{\}\} = \{\{\}\} \\ \displaystyle f(3) &\displaystyle = &\displaystyle f((2 \times 1 + 1)2^0) = f(1) + \omega^{f(0)} \times 1 = \{\{\}\} + \omega^{\{\}} \times 1 = \{\{\}\} \cup \{\{\{\}\}\} = \{\{\},\{\{\}\}\} \end{array} $

as shown above.

 

Non-negative integers $N$ and $M$ are given as input.

Determine whether $f(N) \in f(M)$ holds.

Input

The input is given from standard input in $2$ lines in the following format:

On line $1$, $N$ is given in base $2$ notation.

On line $2$, $M$ is given in base $2$ notation.

Constraints

The input satisfies the following constraints:

  • $N$ is a non-negative integer less than $2^{10^5}$
  • $M$ is a non-negative integer less than $2^{10^5}$

Output

Print Yes if $f(N) \in f(M)$ holds, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
0
0
Output
No

We have $f(0) = \{\}$. $\{\} \in \{\}$ does not hold.

Sample 2
Input
0
1
Output
Yes

We have $f(0) = \{\}$ and $f(1) = \{\{\}\}$. $\{\} \in \{\{\}\}$ holds.

Sample 3
Input
1
11

Note that the input is given in base $2$ notation.

Output
Yes

We have $f(1) = \{\{\}\}$ and $f(3) = \{\{\},\{\{\}\}\}$. $\{\{\}\} \in \{\{\},\{\{\}\}\}$ holds.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。