Решение задачи "Последовательность Фибоначчи" с Меньшиков

Без пояснения   Просмотров: 16


{Fk} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи Fk = Fk - 1 + Fk - 2 (для любого целого k). Даны i, Fi, j, Fj, n (i <> j). Найти Fn. Пример части последовательности:

k -2 -1 0 1 2 3 4 5 6
Fk -5 4 -1 3 2 5 7 12 19
Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= Fk <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Код

#include <iostream>
#include <cstdio>
#include <stdlib.h>
 
using namespace std;
 
int n,i,j;
long long Fi,Fj;
void input()
{
    cin>>i>>Fi>>j>>Fj>>n;
}
//                       F[i]         F[i+1]
long long Fib(long long prev, long long cur, int n)
{
    // forward
    if (n > i) {
        for (int pos = i + 2; pos <= n; pos++) {
            prev += cur;
            swap(cur, prev);
        }
        return cur;
    }
    // back
    else {
        for (int pos = i - 1; pos>=n; pos--) {
            cur -= prev;
            swap(cur, prev);
        }
        return prev;
    }
}
void solve()
{
    if (n == i) { cout<<Fi; return; }
    if (n == j) { cout<<Fj; return; }
 
    if (i > j) {
        swap(i,j);
        swap(Fi,Fj);
    }
 
    if (j == i + 1)
    {
        cout<<Fib(Fi,Fj,n);
        return;
    }
 
    long long l = -2e9 - 10, r = 2e9 + 10;
    while (l<=r)
    {
        long long FiNxt = (l+r)/2;
        long long FjPos = Fib(Fi,FiNxt, j);
        if (FjPos < Fj)
            l = FiNxt + 1;
        else if (FjPos > Fj)
            r = FiNxt - 1;
        else {
            cout<<Fib(Fi,FiNxt,n);
            return;
        }
    }
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться