From the description of this problem we can easily draw the recurrence of
f(n) = 2*f(n-k) + 2^k - 1
and the base cases of
f(0) = 0 and f(1) = 1
However, how can we determine which k would give the minimum value of f(n)?
Suppose k is giving the minimum value, then it must satisfy
2*f(n-k) + 2^k - 1 <= 2*f(n-(k+1)) + 2^(k+1) - 1,
which can be deduced to
f(n-k) - f(n-k-1) <= 2^(k-1).
Thus, let d(n) = f(n) - f(n-1), and we can use d(n) to determine the value
of k through the inequality of
d(n-k) <= 2^(k-1)
and the fact that d(n) is a non-decreasing sequence.
Code:
- /***************************************************************************
- * Copyright (C) 2008 by Liu Kaipeng *
- * LiuKaipeng at gmail dot com *
- ***************************************************************************/
- /* @JUDGE_ID 00000 10254 C++ "The Priest Mathematician" */
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- #include <deque>
- #include <fstream>
- #include <iostream>
- #include <list>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <vector>
- #include "big_unsigned.hpp"
- using namespace std;
- /*
- * From the description of this problem we can easily draw the recurrence of
- * f(n) = 2*f(n-k) + 2^k - 1
- * and the base cases of
- * f(0) = 0 and f(1) = 1
- * However, how can we determine which k would give the minimum value of f(n)?
- * Suppose k is giving the minimum value, then it must satisfy
- * 2*f(n-k) + 2^k - 1 <= 2*f(n-(k+1)) + 2^(k+1) - 1,
- * which can be deduced to
- * f(n-k) - f(n-k-1) <= 2^(k-1).
- * Thus, let d(n) = f(n) - f(n-1), and we can use d(n) to determine the value
- * of k through the inequality of
- * d(n-k) <= 2^(k-1)
- * and the fact that d(n) is a non-decreasing sequence.
- */
- int const size = 10001;
- big_unsigned numbers[size];
- big_unsigned pow2[1500];
- big_unsigned diff[size];
- void gen_numbers()
- {
- pow2[0] = 1;
- for (int n = 1; n < 1500; ++n)
- pow2[n] = pow2[n-1] * 2;
- numbers[0] = 0, numbers[1] = 1;
- diff[0] = 0, diff[1] = 1;
- int k = 1;
- for (int n = 2; n < size; ++n) {
- if (diff[n-k] > pow2[k-1]) ++k;
- numbers[n] = numbers[n-k] * 2;
- numbers[n] += pow2[k];
- numbers[n] -= 1;
- diff[n] = numbers[n] - numbers[n-1];
- }
- }
- int main(int argc, char *argv[])
- {
- #ifndef ONLINE_JUDGE
- freopen((string(argv[0]) + ".in").c_str(), "r", stdin);
- freopen((string(argv[0]) + ".out").c_str(), "w", stdout);
- #endif
- gen_numbers();
- for (int n; cin >> n; ) cout << numbers[n] << '/n';
- return 0;
- }