POJ 2116 - Death to Binary?

http://poj.org/problem?id=2116

概要

0 と 1 の列からなり，右から i 番目のビットの weight がフィボナッチ数列の i 項目であるような Fibonacci-base の数を考える． 「1 のビットが隣り合ってはならない」とすると，表現は一意になる．この表現のしかたを canonical と呼ぶ．

2つの Fibonacci-base な数 (canonical とは限らない) が与えられたとき，それぞれの canonical な表現と，和の canonical な表現を答える．

制約

• 与えられる数は Fibonacci-base で 40 桁まで

解法

やるだけ．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long fib[45];
 5 
 6 long long decode(const string& s)
 7 {
 8   long long x = 0;
 9   const int len = s.size();
10   for (int i = 0; i < len; i++) {
11     if (s[i] == '1') {
12       x += fib[len-i-1];
13     }
14   }
15   return x;
16 }
17 
18 string encode(long long x)
19 {
20   if (x == 0) {
21     return "0";
22   }
23   string s(41, '0');
24   for (int i = 40; i >= 0; i--) {
25     if (x >= fib[i]) {
26       s[40-i] = '1';
27       x -= fib[i];
28     }
29   }
30   return s.substr(s.find('1'));
31 }
32 
33 void times(int n, char c)
34 {
35   for (int i = 0; i < n; i++) {
36     cout << c;
37   }
38 }
39 
40 int main()
41 {
42   fib[0] = 1;
43   fib[1] = 2;
44   for (int i = 2; i <= 41; i++) {
45     fib[i] = fib[i-1] + fib[i-2];
46   }
47 
48   string a, b;
49   while (cin >> a >> b) {
50     long long x = decode(a), y = decode(b);
51     a = encode(x);
52     b = encode(y);
53     const string c = encode(x+y);
54     int len = c.size();
55     cout << "  "; times(len - a.size(), ' '); cout << a << endl;
56     cout << "+ "; times(len - b.size(), ' '); cout << b << endl;
57     cout << "  "; times(len, '-');  cout << endl;
58     cout << "  " << c << endl;
59     cout << endl;
60   }
61   return 0;
62 }