|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <math.h> #include <map> #include <stdio.h> #include <string> #include <vector> using namespace std; map<int,int> mp; int fib[50]; double dp[1010]; int main() { fib[0]=0; fib[1]=1; fib[2]=2; mp[1]=1; mp[2]=2; for(int i=3;i<=20;i++) { fib[i]=fib[i-1]+fib[i-2]; mp[fib[i]]=i; } dp[1]=.4; for(int i=1;i<=1000;i++) { double p=i*1.6; double d=1000000; for(int j=1;j<=18;j++) { if(i-fib[j]>=0) { int a=mp[fib[j]]; double x; if((fib[a+1]+dp[i-fib[j]]-p)<0) { x=-1*(fib[a+1]+dp[i-fib[j]]-p); } else x=(fib[a+1]+dp[i-fib[j]]-p); if(x<d) { d=x; dp[i]=fib[a+1]+dp[i-fib[j]]; } } } } int n; while(cin>>n) { if(n==0) break; printf("%.2lf\n",fabs(dp[n]-n*1.6));//"\n"; } return 0; } |