4586: 最早对决(第2题)
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
小X和小Y凭借出色的程序设计能力,顺利入选了“我们爱科学”活动,该活动以科学精神、创新意识、实践能力的培养为目标,激发广大中小学生爱科学、学科学、用科学的兴趣。
报到之后小X和小Y有幸被分进了人工智能(简称AI)班,经过一周紧张刺激的AI学习,每位同学都编写了一个AI程序“黑白棋”,经过对弈平台的双循环赛,一共选出了32位种子选手,编号分别为1~32,其余选手均为非种子选手,编号为33~128。
最后的决战拉开帷幕,比赛采用淘汰赛制,共有128位选手参加这场淘汰赛,两两对决,胜者进入下一轮,而输的将被直接淘汰出局。通过抽签产生这128位选手的对阵表,抽签规则如下:
首先将种子选手的编号从小到大排序,1号种子安排在1号位置,2号种子安排在128号位置。接着将整个赛区分为上半赛区和下半赛区,即上半赛区是1~64号位置,下半赛区是65~128号位置,将上半赛区的最后一个位置和下半赛区的第一个位置选出来(64号和65号),然后将接下来的2位种子选手(3号和4号)通过随机抽签的方式安排在这2个位置中,也就是说3号种子既可能抽到64号位置,也可能抽到65号位置,3号种子的位置通过抽签定下来之后,4号种子就自动被安排到另一个位置;接下去对于每个赛区再继续分上半赛区和下半赛区,这样就形成了1~32,33~64,65~96,97~128四个赛区,将所有上半赛区的最后一个位置和下半赛区的第一个位置选出来(32号,33号,96号,97号)。然后将接下来的4位种子选手(5号,6号,7号,8号)通过随机抽签的方式安排到这4个位置中,然后继续划分赛区,直到所有种子选手被安排完毕,剩下的96个非种子选手通过随机抽签安排到余下空位中。
小X和小Y的AI十分强大,两人的AI可以打败除了他们以外的所有对手,但是他们发现,假如小X的编号是1号,小Y的编号是2号,他们将作为头两号种子坐在1号位置和128号位置,两人将所向披靡一路击败所有的对手,直到决赛(第7轮)才会相遇。
现在给出小X和小Y的编号,他们想知道最早会在哪一轮相遇?
输入
输入数据仅有一行包含两个用空格隔开的正整数S和T,表示小X和小Y的编号。
输出
输出数据仅有一行包含一个正整数,表示他们最早相遇的轮数。
第1轮:128进64
第2轮:64进32
第3轮:32进16
第4轮:16进8
第5轮:8进4
第6轮:半决赛
第7轮:决赛
样例输入 复制
1 3
样例输出 复制
6
提示
小 X 是 1 号种子,坐在 1 号位置,小 Y 是 3 号种子,他可能抽到 64 号或 65 号位置,如果小 Y 抽到 64 号位置,他跟小 X 会在半决赛(第 6 轮)相遇。如果小 Y 抽到 65 号位置,他跟小 X 会在决赛(第 7 轮)相遇。所以他们最早会在第 6 轮相遇。
数据规模与约定:
对于10%的数据,小X和小Y都是非种子选手即编号都大于32
对于另外10%的数据,小X和小Y有一个是非种子选手
对于100%的数据,1≤S,T≤128
数据规模与约定:
对于10%的数据,小X和小Y都是非种子选手即编号都大于32
对于另外10%的数据,小X和小Y有一个是非种子选手
对于100%的数据,1≤S,T≤128