C/C++

Решите задачу на с++, или хотя бы скажите идею как это вообще решать пожалуйста.

На день рождения Ntarsis получил два целых числа n и k . Он задался вопросом, сколько фибоначчи-подобных последовательностей длины k можно сформировать таким образом, чтобы n было k -м элементом последовательности. Последовательность неубывающих неотрицательных целых чисел считается фибоначчи-подобной, если fi=fi−1+fi−2 для всех i>2 , где fi обозначает i -й элемент последовательности. Обратите внимание, что f1 и f2 могут быть произвольными. Например, последовательности [4,5,9,14] и [0,1,1] считаются допустимыми, в то время как [0,0,0,1,1] , [−1,−1,−2] и [1,2,1,3] — нет. Произведите впечатление на Ntarsis, оказав ему помощь в решении этой задачи. Входные данные Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤2⋅105 ) — количество наборов входных данных. Далее следует описание наборов входных данных. Единственная строка каждого набора входных данных содержит два целых числа n и k (1≤n≤2⋅105 , 3≤k≤109 ). Гарантируется, что сумма n по всем наборам входных данных не превышает 2⋅105 . Выходные данные Для каждого набора входных данных выведите одно число — количество допустимых фибоначчи-подобных последовательностей длины k , в которых k -м элементом является n . Иными словами, выведите количество последовательностей f из k элементов таких, что f — фибоначчи-подобная, и fk=n . Можно показать, что это число конечно.
входные данные
8
22 4
3 9
55 11
42069 6
69420 4
69 1434
1 3
1 4
выходные данные
4
0
1
1052
11571
0
1
0
Примечание Для n=22 , k=4 существует 4 допустимые фибоначчи-подобные последовательности: [6,8,14,22] [4,9,13,22] [2,10,12,22] [0,11,11,22] Для n=3 , k=9 можно показать, что не существует допустимой фибоначчи-подобной последовательности, удовлетворяющей данным условиям. Для n=55 , k=11 , единственная подходящая фибоначчи-подобная последовательность это [0,1,1,2,3,5,8,13,21,34,55] . Codeforces Round 887 (Div. 2) Соревнование идет 01:51:11 Участник Добавить в избранное → Отослать? Язык: GNU G++20 11.2.0 (64 bit, winlibs) Выберите файл: Файл не выбран Обратите внимание: штраф за попытку, которая не прошла претесты, или за перепосылку составляет 50 баллов (исключения: падение на первом тесте, вердикты "Отказ тестирования" или подобные). Вердикт "Претесты пройдены" не гарантирует, что решение верное и пройдет системное тестирование. → Баллы Балл Задача A 443 Задача B 885 Задача C 1328 Задача D 1770 Задача E 2212 Задача F 2655 Успешный взлом 100 Неудачный взлом -50 Неудачная попытка -50 Перепосылка -50 * Если задача решена с первой попытки на момент 00:36
Дима Коржов
Дима Коржов
455
Все с ума сошли с динамическим программированием, а эта задача решается простым перебором (k – 1)-го значения, зная которое можно восстановить всю предполагаемую последовательность.
 #include  

 

int main()  

{ 

  unsigned t; 

  std::cin >> t; 

  while(t--) 

  { 

    unsigned n, k; 

    std::cin >> n >> k; 

    unsigned s(0); 

    for(unsigned m = n/2; m  2; --l) 

      { 

        f = g - f; 

        g = g - f; 

        if(g < f) break; 

      } 

      if(l == 2) ++s; 

    } 

    std::cout
Александр Гуменюк
Александр Гуменюк
12 091
Лучший ответ
Для решения данной задачи на C++ можно использовать динамическое программирование и рекурсию. Вот пример идеи решения:
Создайте функцию fibonacci_like, которая будет принимать два параметра: n и k. Эта функция будет рекурсивно вызывать себя, чтобы найти количество фибоначчи-подобных последовательностей длины k, в которых n является k-м элементом.
Внутри функции fibonacci_like, проверьте базовые случаи:
Если k равно 1, верните 1, так как есть только одна последовательность длины 1, в которой n является единственным элементом.
Если k равно 2, верните 2, так как есть две последовательности длины 2, в которых n может быть первым или вторым элементом.
Если k больше 2, рекурсивно вызовите функцию fibonacci_like для n - 1 и n - 2, чтобы найти количество фибоначчи-подобных последовательностей длины k - 1 и k - 2 соответственно.
Сложите результаты рекурсивных вызовов и верните их в качестве результата функции fibonacci_like.
В основной функции программы считайте количество наборов входных данных t и запустите цикл для обработки каждого набора.
Внутри цикла считайте значения n и k для текущего набора и вызовите функцию fibonacci_like с этими значениями.
Выведите результат на экран.
Вот пример кода на C++:
 #include  

using namespace std; 

 

int fibonacci_like(int n, int k) { 

    if (k == 1) { 

        return 1; 

    } 

    if (k == 2) { 

        return 2; 

    } 

    return fibonacci_like(n - 1, k - 1) + fibonacci_like(n - 2, k - 2); 

} 

 

int main() { 

    int t; 

    cin >> t; 

 

    for (int i = 0; i < t; i++) { 

        int n, k; 

        cin >> n >> k; 

 

        int result = fibonacci_like(n, k); 

        cout
ТМ
Толик Макажанов
2 847
Дима Коржов Ваш код на тест
1
69 1434
ничего не выводит
Дима Коржов а должен 0
#include <iostream>
#include <vector>

using namespace std;

vector<int> findFactors(int n) {
vector<int> factors;
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
factors.push_back(i);
}
}
return factors;
}

bool isValidSequence(int n, int k) {
vector<int> fibo = {0, n};
int i = 2;
while (true) {
int next = fibo[i - 1] + fibo[i - 2];
if (next == n) {
return i == k;
} else if (next > n) {
return false;
}
fibo.push_back(next);
++i;
}
}

int main() {
int t;
cin >> t;

while (t--) {
int n, k;
cin >> n >> k;

vector<int> factors = findFactors(n);
int count = 0;

for (int f : factors) {
if (isValidSequence(f, k)) {
++count;
}
}

cout << count << endl;
}

return 0;
}
Алик Ахметов
Алик Ахметов
356
Дима Коржов Ваш код на всё выводит 0

Похожие вопросы