v 0. Pasted by slipstak2 as cpp at 2011-01-08 14:29:19 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 13.
  2. // 13B. Последовательность Фибоначчи [fiboseq]
  3. // Бинарный поиск
  4. // ibelyaev: 06Jan2011
  5.  
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <stdlib.h>
  9.  
  10. using namespace std;
  11.  
  12. int n,i,j;
  13. long long Fi,Fj;
  14. void input()
  15. {
  16.     cin>>i>>Fi>>j>>Fj>>n;
  17. }
  18. //                       F[i]         F[i+1]
  19. long long Fib(long long prev, long long cur, int n)
  20. {
  21.     // forward
  22.     if (n > i) {
  23.         for (int pos = i + 2; pos <= n; pos++) {
  24.             prev += cur;
  25.             swap(cur, prev);
  26.         }
  27.         return cur;
  28.     }
  29.     // back
  30.     else {
  31.         for (int pos = i - 1; pos>=n; pos--) {
  32.             cur -= prev;
  33.             swap(cur, prev);
  34.         }
  35.         return prev;
  36.     }
  37. }
  38. void solve()
  39. {
  40.     if (n == i) { cout<<Fi; return; }
  41.     if (n == j) { cout<<Fj; return; }
  42.  
  43.     if (i > j) {
  44.         swap(i,j);
  45.         swap(Fi,Fj);
  46.     }
  47.  
  48.     if (j == i + 1)
  49.     {
  50.         cout<<Fib(Fi,Fj,n);
  51.         return;
  52.     }
  53.  
  54.     long long l = -2e9 - 10, r = 2e9 + 10;
  55.     while (l<=r)
  56.     {
  57.         long long FiNxt = (l+r)/2;
  58.         long long FjPos = Fib(Fi,FiNxt, j);
  59.         if (FjPos < Fj)
  60.             l = FiNxt + 1;
  61.         else if (FjPos > Fj)
  62.             r = FiNxt - 1;
  63.         else {
  64.             cout<<Fib(Fi,FiNxt,n);
  65.             return;
  66.         }
  67.     }
  68. }
  69. int main()
  70. {
  71.     freopen("input.txt","r",stdin);
  72.     freopen("output.txt","w",stdout);
  73.  
  74.     input();
  75.     solve();
  76.     return 0;
  77. }


Editing is locked.