1
0

Ural1396.dpr 2.0 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
  1. {$IFDEF ONLINE_JUDGE}
  2. {$I-,R-,D-,Q-,S-}
  3. {$MODE DELPHI}
  4. {$ENDIF}
  5. {
  6. 1754550 18:28:08 4 Sep 2007 Scale Rhyme 1396 Pascal Wrong answer 1 0.093 208 KB
  7. 1754567 18:39:12 4 Sep 2007 Scale Rhyme 1396 Pascal Accepted 0.078 208 KB
  8. }
  9. Program ScaleRhyme_Ural1396;
  10. Const
  11. Inpath = 'ural.in' ;
  12. Outpath = 'ural.out' ;
  13. Precision = 1E-10 ;
  14. Type
  15. TIndex = Longint ;
  16. TData = Extended ;
  17. TMem = Record
  18. A,B:TData;
  19. End;
  20. Var
  21. N:TData;
  22. F:Array [1..63] Of TMem;
  23. Procedure Init;
  24. Var
  25. I:TIndex;
  26. Begin
  27. F[1].A := 1 ;
  28. F[1].B := 0 ;
  29. F[2].A := 0 ;
  30. F[2].B := 1 ;
  31. For I := 3 To 63 Do
  32. Begin
  33. F[I].A := F[I - 1].A + F[I - 2].A ;
  34. F[I].B := F[I - 1].B + F[I - 2].B ;
  35. End;
  36. End;
  37. Function Max(A,B:TData):TData;
  38. Begin
  39. If A > B Then Result := A
  40. Else Result := B ;
  41. End;
  42. Function Ans(Left,Right:TData;Count:TIndex;LeftValue,RightValue:TData):TData;
  43. Var
  44. Mid,MidValue:TData;
  45. Begin
  46. Mid := (Left + Right)/2 ;
  47. MidValue := LeftValue + RightValue ;
  48. If Mid - Precision <= N + 1 Then
  49. Begin
  50. If Abs(Count - 1) < Precision Then
  51. Result := LeftValue
  52. Else
  53. If LeftValue < MidValue Then
  54. Result := LeftValue * F[Count + 1].A + MidValue * F[Count + 1].B
  55. Else
  56. Result := MidValue * F[Count + 1].A + LeftValue * F[Count + 1].B ;
  57. If N >= Mid - Precision Then
  58. Result := Max(Result,Ans(Mid,Right,Count - 1,MidValue,RightValue)) ;
  59. End
  60. Else
  61. Result := Ans(Left,Mid,Count - 1,LeftValue,MidValue) ;
  62. End;
  63. Procedure Main;
  64. Var
  65. Left,Right:TData;
  66. Count:TIndex;
  67. Begin
  68. ReadLn(N);
  69. Repeat
  70. Left := 1 ;
  71. Count := 0 ;
  72. While Left * 2 <= N Do
  73. Begin
  74. Left := Left * 2 ;
  75. Count := Count + 1 ;
  76. End;
  77. Right := Left * 2 ;
  78. WriteLn(Max(F[Count + 1].A + F[Count + 1].B,Ans(Left,Right,Count,1,1)):0:0);
  79. ReadLn(N);
  80. Until N = 0 ;
  81. End;
  82. Begin
  83. {$IFNDEF ONLINE_JUDGE}
  84. Assign(Input,Inpath);
  85. Reset(Input);
  86. Assign(Output,Outpath);
  87. Rewrite(Output);
  88. {$ENDIF}
  89. Init;
  90. Main;
  91. {$IFNDEF ONLINE_JUDGE}
  92. Close(Input);
  93. Close(Output);
  94. {$ENDIF}
  95. End.