2015年7月25日 星期六

[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) ;
    }
}
 

沒有留言:

張貼留言