// 这次介绍一道 TJU 上的题: Kitty 猫的基因编码版本 1/2
// http://acm.tongji.edu.cn/people/ps/showproblem.php?problem_id=1096
// http://acm.tongji.edu.cn/people/ps/showproblem.php?problem_id=1173

// 这道题是 NOIP2004 普及组中 FBI 树的相似题, 算法基本上是没有区别
// 由于基因的长度是 2^k, 这就给了我们一个 dfs 算法的提示.

// 算法的描述基本这样:
// 构造一个二元树, 根就是原基因
// 然后左儿子就是基因的左边一半, 右儿子就是基因的右边,
// 最后直到某个儿子的内容都相同 (都是 0 或者都是 1) 就返回
// 否则继续 dfs 分析

Run ID User      Problem Result   Memory Time   Language Date  
243738 davidw017 1096    Accepted 44k    1 ms   C++      2005-05-15 17:13:39
243747 davidw017 1173    Accepted 188k   156 ms C++      2005-05-15 17:15:54

#include <stdio.h>
#include <string.h>

#define MAXN 256
/* 这里控制基因串的长度, 对于 1096 长度只有 2^8 = 256 个字节这里就定义为 256,
   对于 1173 长度有 2^17 = 131072 就要改成 131072, 即
   #define MAXN 131072
*/
char dnacode[MAXN];

bool enable[2];
/* enable[0] 的取值代表基因中 0 是否出现, enable[1] 即表示 1. */

/* 深度优先搜索过程
   char *code 表示要分析的基因, int length 表示基因的长度.
*/
void dfs(char *code, int length)
{
  if (length == 0) return;
  /* 如果基因长度等于 0 就返回 */

  memset (enable, false, sizeof(enable));
  for (int index = 0; index < length; index++)
    enable[code[index] - 48] = true;
  /* 清空 enable 数组, 然后分析基因, 若出现过 0 就把 enable[0] 置为 true,
     出现过 1 就把 enable[1] 置成 true. */

  if (enable[0] == true && enable[1] == true)
  /* 如果 0 和 1 都出现过, 那么相应的情况就应该是 C */
    printf("C");
  else if (enable[0] == true)
  /* 如果只是 0 出现过就是 A */
    printf("A");
  else if (enable[1] == true)
  /* 如果只是 1 出现过就是 B */
    printf("B");

  if (enable[0] == enable[1])
  {
    dfs (code, length/2);
    dfs (code + length/2, length/2);
  }
  /* 如果 enable[0] = enable[1] = true, 都出现过, 就说明需要继续分析
     按题目描述把基因段 code 等分为两个串, 继续搜索 */
}

int main()
{
  while (scanf("%s", dnacode) != EOF)
  {
    dfs (dnacode, strlen(dnacode));
    memset (dnacode, 0, sizeof(dnacode));
    printf ("\n");
  }
  /* 读入数据 - dfs - 清空数组 - 回车
  */
}