[HOJ 278] Many Prizes

作法：

我們只要知道一個人最好是可以到多少，還有最差可以到多少，就可以分別對兩個答案二分搜了。首先看一個人最好可以到多少，最佳情形當然是他剛好一直遇到比他弱的，所以一直贏，直到沒有人比弱為止開始一直輸。假設現在比他弱的人有$x$個，那麼不難得出下一輪比他弱的只會剩$\left \lfloor \frac{x-1}{2} \right \rfloor $個，因此只要一直除下去直到這數字變$0$為止，就知道他可以連續贏幾場了。並且一個人的最差狀況則是一直輸，最後再一直贏，也可以用類似的方法求出會先輸幾場才開始一直贏。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int n ;
LL best(LL x)
{
    int num=0 ;
    for(LL now=(1LL<<n)-x-1;now;now=(now-1)/2) num++ ;
    return (1LL<<(n-num))-1 ;
}
LL worst(LL x)
{
    int num=0 ;
    for(LL now=x;now;now=(now-1)/2) num++ ;
    return (1LL<<n)-(1LL<<(n-num)) ;
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        LL p ; scanf("%d%lld",&n,&p) ; p-- ;
        LL l=0 , r=(1LL<<n) ;
        while(r-l>1)
        {
            LL mid=(l+r)/2 ;
            if(worst(mid)<=p) l=mid ;
            else r=mid ;
        }
        printf("%lld ",l) ; l=0 , r=(1LL<<n) ;
        while(r-l>1)
        {
            LL mid=(l+r)/2 ;
            if(best(mid)<=p) l=mid ;
            else r=mid ;
        }
        printf("%lld\n",l) ;
    }
}