#include <stdio.h> typedef struct tree { struct tree *t[3]; } tree; typedef struct list { tree *t; struct list *n; } list; list list_pool[20000000] = {}; int list_used = 0; tree tree_pool[20000000] = {}; int tree_used = 0; tree *str2tree_rec (char *s, int *idx) { tree *ans = NULL; if (s[*idx] != '(') { return NULL; } ans = tree_pool+tree_used; tree_used++; *idx += 1; ans->t[0] = str2tree_rec(s, idx); *idx += 1; ans->t[1] = str2tree_rec(s, idx); *idx += 1; ans->t[2] = str2tree_rec(s, idx); return ans; } tree *str2tree (char *s) { int idx = 0; return str2tree_rec(s, &idx); } void tree2str_rec (tree *t, char *buf, int *idx) { if (t == NULL) { return; } buf[*idx] = '('; *idx += 1; tree2str_rec(t->t[0], buf, idx); buf[*idx] = '|'; *idx += 1; tree2str_rec(t->t[1], buf, idx); buf[*idx] = ')'; *idx += 1; tree2str_rec(t->t[2], buf, idx); buf[*idx] = '\0'; return; } void tree2str (tree *t, char *buf) { int idx = 0; tree2str_rec(t, buf, &idx); return; } tree *copy_tree (tree *t) { tree *ans = NULL; if (t != NULL) { return NULL; } ans = tree_pool+tree_used; tree_used++; ans->t[0] = copy_tree(t->t[0]); ans->t[1] = copy_tree(t->t[1]); ans->t[2] = copy_tree(t->t[2]); return ans; } tree *get_zero_tree (tree *t) { tree *ans = NULL; if (t == NULL || (t->t[0] == NULL && t->t[1] == NULL && t->t[2] == NULL)) { return NULL; } ans = tree_pool+tree_used; tree_used++; if (t->t[2] != NULL) { ans->t[0] = copy_tree(t->t[0]); ans->t[1] = copy_tree(t->t[1]); ans->t[2] = get_zero_tree(t->t[2]); return ans; } if (t->t[0] == NULL) { ans->t[1] = get_zero_tree(t->t[1]); return ans; } if (t->t[1] == NULL) { ans->t[0] = get_zero_tree(t->t[0]); return ans; } if (t->t[1]->t[2] == NULL || t->t[1]->t[2]->t[0] != NULL || t->t[1]->t[2]->t[1] != NULL || t->t[1]->t[2]->t[2] != NULL) { ans->t[0] = copy_tree(t->t[0]); ans->t[1] = get_zero_tree(t->t[1]); return ans; } ans->t[0] = get_zero_tree(t->t[0]); ans->t[1] = tree_pool+tree_used; tree_used++; ans->t[1]->t[0] = copy_tree(t->t[0]); ans->t[1]->t[1] = get_zero_tree(t->t[1]); ans->t[1]->t[2] = tree_pool+tree_used; tree_used++; return ans; } void trans_single_head (tree *t) { if (t == NULL) { return; } if (t->t[0] == NULL || t->t[1] == NULL) { trans_single_head(t->t[0]); trans_single_head(t->t[1]); trans_single_head(t->t[2]); return; } if (t->t[1]->t[2] != NULL) { tree *t1 = t->t[1]; tree *t2 = t->t[2]; tree *cp = copy_tree(t->t[0]); tree *new_t2 = t1; tree *tmp = t; t->t[1] = NULL; while (cp != NULL) { tree *new = tree_pool+tree_used; tree_used++; new->t[0] = cp; new->t[2] = new_t2; new_t2 = new; cp = get_zero_tree(cp); } t->t[2] = new_t2; while (tmp->t[2] != NULL) { tmp = tmp->t[1]; } tmp->t[2] = t2; trans_single_head(t->t[0]); trans_single_head(t->t[2]); return; } t->t[1]->t[2] = t->t[2]; t->t[2] = t->t[1]; t->t[1] = NULL; trans_single_head(t->t[0]); trans_single_head(t->t[2]); return; } int compare (tree *t1, tree *t2, int alt); int compare_rec (tree *t1, tree *t2) { int res = 0; int tmp = 0; if (t2 == NULL) { return 1; } if (t2->t[0] != NULL && compare(t2->t[0], t1, 1) > 0) { return -1; } res = compare_rec(t1, t2->t[1]); if (res < 0) { return -1; } tmp = compare_rec(t1, t2->t[1]); if (tmp < 0) { return -1; } return 1; } int compare (tree *t1, tree *t2, int alt) { list *l1 = NULL; list *l2 = NULL; tree *tmp_tree = t1; int res = 0; while (tmp_tree != NULL) { list *tmp_list = list_pool+list_used; list_used++; tmp_list->t = tmp_tree; tmp_list->n = l1; l1 = tmp_list; tmp_tree = tmp_tree->t[2]; } tmp_tree = t2; while (tmp_tree != NULL) { list *tmp_list = list_pool+list_used; list_used++; tmp_list->t = tmp_tree; tmp_list->n = l2; l2 = tmp_list; tmp_tree = tmp_tree->t[2]; } while (l1 != NULL && l2 != NULL) { if (l1->t->t[0] == NULL && l1->t->t[1] == NULL) { if (l2->t->t[0] == NULL && l2->t->t[1] == NULL) { l2 = l2->n; } else { alt = 1; } l1 = l1->n; } else if (l2->t->t[0] == NULL && l2->t->t[1] == NULL) { alt = 0; l2 = l2->n; } else if (l1->t->t[0] != NULL && l2->t->t[0] != NULL) { res = compare(l1->t->t[0], l2->t->t[0], alt); if (res > 0) { l2 = l2->n; alt = 0; } else { l1 = l1->n; alt = 1; } } else if (l1->t->t[1] != NULL && l2->t->t[1] != NULL) { res = compare(l1->t->t[1], l2->t->t[1], alt); if (res > 0) { l2 = l2->n; alt = 0; } else { l1 = l1->n; alt = 1; } } else if (l1->t->t[0] != NULL) { res = compare_rec(l1->t->t[0], l2->t->t[1]); if (res > 0) { l2 = l2->n; alt = 0; } else { l1 = l1->n; alt = 1; } } else { res = compare_rec(l2->t->t[0], l1->t->t[1]); if (res > 0) { l1 = l1->n; alt = 1; } else { l2 = l2->n; alt = 1; } } } if (l2 != NULL || (l1 == NULL && l2 == NULL && alt <= 0)) { return 0; } return 1; } int main () { char t0[31] = ""; char t1[31] = ""; int res = 0; tree *t0_tree = NULL; tree *t1_tree = NULL; list *cnt[2] = {}; char buf[1000001] = ""; res = scanf("%s", t0); res = scanf("%s", t1); t0_tree = str2tree(t0); t1_tree = str2tree(t1); trans_single_head(t0_tree); trans_single_head(t1_tree); res = compare(t0_tree, t1_tree, 0); if (res > 0) { printf("0\n"); } else { printf("1\n"); } return 0; }