#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include using namespace std; // 型名の短縮 using ll = long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vvvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; template using priority_queue_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); const vi DX = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左) const vi DY = { 0, 1, 0, -1 }; int INF = 1001001001; ll INFL = 4004004003104004004LL; // (int)INFL = 1010931620; double EPS = 1e-15; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x)) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x)) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 #define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定 // 汎用関数の定義 template inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template inline T get(T set, int i) { return (set >> i) & T(1); } // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v) --x; return v; } template inline vector& operator++(vector& v) { repea(x, v) ++x; return v; } #endif // 折りたたみ用 #if __has_include() #include using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif //using mint = modint1000000007; using mint = modint998244353; //using mint = modint; // mint::set_mod(m); namespace atcoder { inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } } using vm = vector; using vvm = vector; using vvvm = vector; using vvvvm = vector; #endif #ifdef _MSC_VER // 手元環境(Visual Studio) #include "local.hpp" #else // 提出用(gcc) inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define gcd __gcd #define dump(...) #define dumpel(v) #define dump_list(v) #define dump_mat(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) while (1) cout << "OLE"; } #endif tuple sep(const string& t) { Assert(!t.empty()); int n = sz(t); string t1, t2, t3; vi cnt(3); int l = 1; rep(i, n) { if (t[i] == '(') cnt[0]++; else if (t[i] == '|') cnt[1]++; else cnt[2]++; if (cnt[0] == cnt[1] && cnt[1] - 1 == cnt[2] && t[i] == '|') { t1 = t.substr(l, i - l); l = i + 1; } else if (cnt[0] == cnt[1] && cnt[1] == cnt[2] && t[i] == ')') { t2 = t.substr(l, i - l); l = i + 1; break; } } t3 = t.substr(l); return { t1, t2, t3 }; } map, string> dp; string f(const string& t, int n) { if (t == "") return ""; if (dp.count({ t, n })) return dp[{t, n}]; auto [t0, t1, t2] = sep(t); if (t2 != "") { dp[{t, n}] = "(" + t0 + "|" + t1 + ")" + f(t2, n); } else if (t0 == "" && t1 == "") { dp[{t, n}] = ""; } else if (t0 == "") { if (n == 0) dp[{t, n}] = "(|" + f(t1, 0) + ")"; else dp[{t, n}] = "(|" + f(t1, n) + ")" + f(t, n - 1); } else if (t1 == "") { if (n == 0) dp[{t, n}] = "(" + f(t0, 0) + "|)"; else dp[{t, n}] = "(" + f(t0, n) + "|" + f(t, n - 1) + ")"; } else if (t1.substr(sz(t1) - 3) == "(|)") { if (n == 0) dp[{t, n}] = "(" + f(t0, 0) + "|(" + t0 + "|" + f(t1, 0) + ")(|))"; else dp[{t, n}] = "(" + f(t0, n) + "|" + f(t, n - 1) + ")"; } else { dp[{t, n}] = "(" + t0 + "|" + f(t1, n) + ")"; } return dp[{t, n}]; } /* 反例 (|)(|(|)(|)) : 1 + ω^2 (|(|)) : ω */ bool WA(const string& a, const string& b) { if (a == "") return true; if (b == "") return false; auto [a0, a1, a2] = sep(a); auto [b0, b1, b2] = sep(b); if (a0 != b0) { return WA(a0, b0); } else if (a1 != b1) { return WA(a1, b1); } else { return WA(a2, b2); } } void zikken() { string s = "((|((|)|))(|)|)"; // 実行するとパソコンが物故割れる //while (s != "") { // dump(s); // s = f(s, 1); //} while (s != "") { dump(s); s = f(s, 0); } exit(0); } void zikken2() { string s = "((|)|(|))"; dump(s, ": "); rep(i, 5) { dump(i, ":", f(s, i), ": "); } exit(0); } /* (|) = f(0|0) = 1 0 : 0 1 : 0 2 : 0 3 : 0 4 : 0 (|(|)) : f(0|1) = ω 0 : (|) : f(0|0) = 1 1 : (|)(|) : 1+1 = 2 2 : (|)(|)(|) : 1+1+1 = 3 3 : (|)(|)(|)(|) : 1+1+1+1 = 4 4 : (|)(|)(|)(|)(|) : 1+1+1+1+1 = 5 (|(|)(|)) : f(0|2) = ω*ω = ω^2 0 : (|(|)) : f(0|1) = ω 1 : (|(|))(|(|)) : ω+ω = ω*2 2 : (|(|))(|(|))(|(|)) : ω+ω+ω = ω*3 3 : (|(|))(|(|))(|(|))(|(|)) : ω+ω+ω+ω = ω*4 4 : (|(|))(|(|))(|(|))(|(|))(|(|)) : ω+ω+ω+ω+ω = ω*5 左側が死んでいれば通常のヒドラゲームと等価みたい.f(0|α) = ω^α とするのが良さそう. ((|)|) : f(1|0) = ω^ω^...^ω = ε_0 0 : (|) : 0 1 : (|(|)) : f(0|1) = ω 2 : (|(|(|))) : f(0|ω) = ω^ω 3 : (|(|(|(|)))) : f(0|ω^ω) = ω^ω^ω 4 : (|(|(|(|(|))))) : f(0|ω^ω^ω) = ω^ω^ω^ω ((|)|(|)) : f(1|1) = ω^ω^...^ω^(ε_0+1) = ε_1 0 : (|((|)|)(|)) : f(0|f(1|0)+f(0|0)) = f(0|ε_0+1) = ω^(ε_0+1) 1 : (|(|((|)|)(|))) : f(0|f(0|f(1|0)+f(0|0))) = f(0|ω^(ε_0+1)) = ω^ω^(ε_0+1) 2 : (|(|(|((|)|)(|)))) : 3 : (|(|(|(|((|)|)(|))))) : 4 : (|(|(|(|(|((|)|)(|)))))) : もしかして正体は 2 変数ヴェブレン関数? https://googology.fandom.com/ja/wiki/%E3%83%B4%E3%82%A7%E3%83%96%E3%83%AC%E3%83%B3%E9%96%A2%E6%95%B0 https://ja.wikipedia.org/wiki/%E3%83%B4%E3%82%A7%E3%83%96%E3%83%AC%E3%83%B3%E9%9A%8E%E5%B1%A4 このように構成されたヴェブレン階層の値は、次のように比較することができる: 次のいずれかが成り立つ場合、 φα(β) < φγ(δ)。 α = γ かつ β < δ α < γ かつ β < φγ(δ) α > γ かつ φα(β) < δ これを再帰的に使う感じ? */ int comp(string a, string b); void shrink(vector& ts) { dump("shrink() :", ts); int i = 0; while (i < sz(ts) - 1) { if (comp(ts[i], ts[i + 1]) == 1) { ts.erase(ts.begin() + i); if (i > 0) i--; } else { i++; } } } vector sep_all(string t) { dump("sep_all() :", t); vector res; while (1) { if (t == "") break; auto [t1, t2, t3] = sep(t); res.push_back("(" + t1 + "|" + t2 + ")"); t = t3; } shrink(res); return res; } int comp_all(vector as, vector bs); int comp(string a, string b) { dump("comp() :", a, b); if (a == "" && b == "") return 0; if (a == "") return 1; if (b == "") return -1; auto [a1, a2, a3] = sep(a); auto [b1, b2, b3] = sep(b); { int c11 = comp_all(sep_all(a1), sep_all(b1)); int c22 = comp_all(sep_all(a2), sep_all(b2)); int c20 = comp_all(sep_all(a2), { b }); int c02 = comp_all({ a }, sep_all(b2)); if (c11 == 0 && c22 == 1) return 1; if (c11 == 1 && c20 == 1) return 1; if (c11 == -1 && c02 == 1) return 1; } swap(a, b); swap(a1, b1); swap(a2, b2); { int c11 = comp_all(sep_all(a1), sep_all(b1)); int c22 = comp_all(sep_all(a2), sep_all(b2)); int c20 = comp_all(sep_all(a2), { b }); int c02 = comp_all({ a }, sep_all(b2)); if (c11 == 0 && c22 == 1) return -1; if (c11 == 1 && c20 == 1) return -1; if (c11 == -1 && c02 == 1) return -1; } return 0; } int comp_all(vector as, vector bs) { dump("comp_all() :", as, bs); int pa = 0, pb = 0; while (1) { if (pa == sz(as) && pb == sz(bs)) return 0; if (pa == sz(as)) return 1; if (pb == sz(bs)) return -1; int c = comp(as[pa], bs[pb]); if (c != 0) return c; pa++; pb++; } return 0; } int main() { input_from_file("input.txt"); // output_to_file("output.txt"); // zikken2(); string a, b; cin >> a >> b; auto as = sep_all(a); auto bs = sep_all(b); auto c = comp_all(as, bs); cout << (c != -1) << endl; }