v 0. Pasted by slipstak2 as cpp at 2011-01-08 14:40:36 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. long long Fib(int n)
  19. {
  20.     long long prev = 1, cur = 1;
  21.     for (int i = 2; i<=n; i++)
  22.     {
  23.         prev += cur;
  24.         swap(cur, prev);
  25.     }
  26.     return cur;
  27. }
  28. //                       F[i]         F[i+1]
  29. long long Fib(long long prev, long long cur, int n)
  30. {
  31.     // forward
  32.     if (n > i) {
  33.         for (int pos = i + 2; pos <= n; pos++) {
  34.             prev += cur;
  35.             swap(cur, prev);
  36.         }
  37.         return cur;
  38.     }
  39.     // back
  40.     else {
  41.         for (int pos = i - 1; pos>=n; pos--) {
  42.             cur -= prev;
  43.             swap(cur, prev);
  44.         }
  45.         return prev;
  46.     }
  47. }
  48. void solve()
  49. {
  50.     if (n == i) { cout<<Fi; return; }
  51.     if (n == j) { cout<<Fj; return; }
  52.  
  53.     if (i > j) {
  54.         swap(i,j);
  55.         swap(Fi,Fj);
  56.     }
  57.  
  58.     // A(i)   = 1 * A(i) + 0 * A(i+1)
  59.     // A(i+1) = 0 * A(i) + 1 * A(i+1)
  60.     // A(i+2) = 1 * A(i) + 1 * A(i+1)
  61.     // A(i+3) = 1 * A(i) + 2 * A(i+1)
  62.     // A(i+4) = 2 * A(i) + 3 * A(i+1)
  63.     // A(i+5) = 3 * A(i) + 5 * A(i+1)
  64.     // A(i+6) = 5 * A(i) + 8 * A(i+1)
  65.  
  66.     // F(0) = 1
  67.     // F(1) = 1
  68.     // F(2) = 2
  69.     // F(3) = 3
  70.     // F(4) = 5
  71.     // F(5) = 8
  72.  
  73.     // A(i+x) = F(x-2) * A(i) + F(x-1) * A(i+1)
  74.     // i + x = j
  75.     // A(j) = F(j-i-2) * A(i) + F(j-i-1) * A(i+1);
  76.     // A(i+1) = [A(j) - F(j-i-2) * A(i)] / F(j-i-1);
  77.     // FiNxt = A(i+1);
  78.    
  79.     int k = j - i;
  80.     long long FiNxt;
  81.     if (k == 1)
  82.         FiNxt = Fj;
  83.     else
  84.         FiNxt =  (Fj - Fib(k-2) * Fi) / Fib(k-1);   
  85.     cout<<Fib(Fi, FiNxt, n);
  86. }
  87. int main()
  88. {
  89.     freopen("input.txt","r",stdin);
  90.     freopen("output.txt","w",stdout);
  91.  
  92.     input();
  93.     solve();
  94.     return 0;
  95. }


Editing is locked.