#B4210. [常州市赛 2022] 最早对决

    ID: 9430 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>2022江苏分支结构分类讨论小学科创活动

[常州市赛 2022] 最早对决

背景

搬运自 http://czoj.com.cn/p/451。数据为民间数据。

题目描述

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

报到之后小 X\text{X} 和小 Y\text{Y} 有幸被分进了人工智能(简称 AI)班,经过一周紧张刺激的AI学习, 每位同学都编写了一个 AI 程序“黑白棋”,经过对弈平台的双循环赛,一共选出了 3232 位种 子选手,编号分别为 1∼321 \sim 32,其余选手均为非种子选手,编号为 33∼12833 \sim 128。 最后的决战拉开帷幕,比赛采用淘汰赛制,共有 128128 位选手参加这场淘汰赛,两两对决, 胜者进入下一轮,而输的将被直接淘汰出局。通过抽签产生这 128128 位选手的对阵表,抽签规则如下:

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

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

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

输入格式

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

输出格式

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

  • 第 11 轮:128128 进 6464;
  • 第 22 轮:6464 进 3232;
  • 第 33 轮:3232 进 1616;
  • 第 44 轮:1616 进 88;
  • 第 55 轮:88 进 44;
  • 第 66 轮:半决赛;
  • 第 77 轮:决赛。
1 3
6

提示

样例解释

小 X\text{X} 是 11 号种子,坐在 11 号位置,小 Y\text{Y} 是 33 号种子,他可能抽到 6464 号或 6565 号位置, 如果小 Y\text{Y} 抽到 6464 号位置,他跟小 X\text{X} 会在半决赛(第 66 轮)相遇。如果小 Y\text{Y} 抽到 6565 号位置,他跟小 X\text{X} 会在决赛(第 77 轮)相遇。所以他们最早会在第 66 轮相遇。

数据规模与约定

对于 10%10\% 的数据,小 X\text{X} 和小 Y\text{Y} 都是非种子选手,即编号都大于 3232;

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

对于 100%100\% 的数据,1≤S,T≤1281≤S,T≤128。