Algoogle

Algorithm for Programming Contest

PKU 3191 The Moronic Cowmpouter

Category: PKU Tag: math

The Moronic Cowmpouter

問題概要


解法


10進数を-2進数に変換せよという問題.
実はほとんど2進数に変換するのと同じようにできる.
Wikipedia Negative Base
なんかあまりが負だったらあまりの方は基数を引いて元の数に1足すらしい.
いくつか実験してみるとわかります

コード


(3191.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>

using namespace std;

int N, base = -2;
int main(){
    cin >> N;
    if(!N){
        cout << 0 << endl;
        return 0;
    }
    vector<int> ans;
    while(N){
        int res = N % (-2);
        N /= -2;
        if(res == -1){
            res = 1;
            N++;
        }
        ans.push_back(res);
    }
    for(int i = ans.size()-1; i >= 0; i--)
        cout << ans[i];
    cout << endl;
    return 0;
}

Comments