3191:The Moronic Cowmpouter

keyword

n進数　C++

概要

x(|x|<2^31)が与えられたときその-2進数表記を出力する問題。
分からなかったので実験。あるビット数以下で表せる数は連続であることに気づく。したがってビット数がn本以下のときの上限と下限を知っておけば、上からビットを立てるべきか立てないべきか判定できる。

int main(){
    int i,pos=0;
    ll n;
    scanf("%lld",&n);
    ll twos[45], ub[45], lb[45];
    twos[0] = 1;
    ub[0] = 1;
    lb[0] = 0;
    REP(i,40) twos[i+1] = -2*twos[i];
    REP(i,40){
        ub[i+1] = max(ub[i], ub[i]+twos[i+1]);
        lb[i+1] = min(lb[i], lb[i]+twos[i+1]);
    }
    string ans="";

    if(n==0){
        printf("0\n");
        return 0;
    }

    for(i=40;i>=0;i--){
        if(!(lb[i] <= n + twos[i] && n + twos[i] <= ub[i])){
            n -= twos[i];
            ans += '1';
        }
        else ans += '0';
    }

    REP(i,40)if(ans[i]=='1')break;
    printf("%s\n",ans.substr(i).c_str());
    return 0;
}