#include <stdio.h> #include <string.h> #include <cmath> #include <vector> using namespace std; #define MAX_FIB_SUM 1000 #define MAX_NEXT_FIB_SUM 1618*2 bool possible[MAX_FIB_SUM + 1][MAX_NEXT_FIB_SUM + 1]; vector<int> fibs; void dp(int fib_sum, int next_fib_sum) { possible[fib_sum][next_fib_sum] = true; for (int i = 0; i < fibs.size() - 1; i++) if (fib_sum + fibs[i] <= MAX_FIB_SUM && !possible[fib_sum + fibs[i]][next_fib_sum + fibs[i + 1]]) { dp(fib_sum + fibs[i], next_fib_sum + fibs[i + 1]); } } int main() { fibs.push_back(1); fibs.push_back(2); do { fibs.push_back(fibs.back() + fibs[fibs.size() - 2]); } while (fibs.back() <= MAX_FIB_SUM); memset(possible, false, sizeof(possible)); possible[0][0] = true; dp(0, 0); while (true) { int fib_sum; scanf("%d", &fib_sum); if (fib_sum == 0) break; int closest_int = fib_sum * 16; closest_int = (closest_int % 10 < 5) ? closest_int / 10 : closest_int / 10 + 1; int diff = 0; while (true) { if (closest_int + diff <= MAX_NEXT_FIB_SUM && possible[fib_sum][closest_int + diff]) break; if (closest_int >= diff && possible[fib_sum][closest_int - diff]) break; diff++; } double smallest_diff; if (closest_int + diff <= MAX_NEXT_FIB_SUM && possible[fib_sum][closest_int + diff]) smallest_diff = fabs(fib_sum * 1.6 - closest_int + diff); if (closest_int >= diff && possible[fib_sum][closest_int - diff] && fabs(fib_sum * 1.6 - closest_int - diff) <= smallest_diff) smallest_diff = fabs(fib_sum * 1.6 - closest_int - diff); printf("%.2f\n", smallest_diff); } return 0; }
Thursday, April 23, 2015
UVa 11780 - Miles 2 Km
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment