UVa 11780 - Miles 2 Km

#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;
}