#451. [CZOI2022 B] 最早对决

[CZOI2022 B] 最早对决

题目描述

小X和小Y凭借出色的程序设计能力,顺利入选了“我们爱科学”活动,该活动以科学精神、创新意识、实践能力的培养为目标,激发广大中小学生爱科学、学科学、用科学的兴趣。

报到之后小X和小Y有幸被分进了人工智能班,经过一周紧张刺激的AI学习,每位同学都编写了一个AI程序“黑白棋”,经过对弈平台的双循环赛,一共选出了 3232 位种子选手,编号分别为 1321\sim32,其余选手均为非种子选手,编号为 3312833\sim128

最后的决战拉开帷幕,比赛采用淘汰赛制,共有 128128 位选手参加这场淘汰赛,两两对决,胜者进入下一轮,而输的将被直接淘汰出局。通过抽签产生这 128128 位选手的对阵表,抽签规则如下:

首先将种子选手的编号从小到大排序,11 号种子安排在 11 号位置,22 号种子安排在 128128 号位置。接着将整个赛区分为上半赛区和下半赛区,即上半赛区是 1641\sim64 号位置,下半赛区是 6512865\sim 128 号位置,将上半赛区的最后一个位置和下半赛区的第一个位置选出来(6464 号和 6565 号),然后将接下来的 22 位种子选手(33 号和 44 号)通过随机抽签的方式安排在这 22 个位置中,也就是说 33 号种子既可能抽到 6464 号位置,也可能抽到 6565 号位置,33 号种子的位置通过抽签定下来之后,44 号种子就自动被安排到另一个位置;接下去对于每个赛区再继续分上半赛区和下半赛区,这样就形成了 132,3364,6596,971281\sim32,33\sim64,65\sim96,97\sim 128 四个赛区,将所有上半赛区的最后一个位置和下半赛区的第一个位置选出来(3232 号,3333 号,9696 号,9797 号)。然后将接下来的 44 位种子选手(55 号,66 号,77 号,88 号)通过随机抽签的方式安排到这 44 个位置中,然后继续划分赛区,直到所有种子选手被安排完毕,剩下的 9696 个非种子选手通过随机抽签安排到余下空位中。

小X和小Y的AI十分强大,两人的AI可以打败除了他们以外的所有对手,但是他们发现,假如小X的编号是 11 号,小Y的编号是 22 号,他们将作为头两号种子坐在 11 号位置和 128128 号位置,两人将所向披靡一路击败所有的对手,直到决赛(第 77 轮)才会相遇。

现在给出小X和小Y的编号,他们想知道最早会在哪一轮相遇?

输入格式

输入数据仅有一行包含两个用空格隔开的正整数 SSTT,表示小X和小Y的编号。

输出格式

输出数据仅有一行包含一个正整数,表示他们最早相遇的轮数。

1 3
6

数据范围

对于 10%10\% 的数据,小X和小Y都是非种子选手,即 S,T32S,T\ge32

对于另外 10%10\% 的数据,小X和小Y有一个是非种子选手。

对于 100%100\% 的数据,1S,T1281\leq S,T\leq 128