Решите задачу на с++, или хотя бы скажите идею как это вообще решать.
На день рождения 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
а ты знаешь, что жульничать во время контеста нехорошо?)
в итоге вместо того, чтобы самостоятельно подумать над нормальным решением, ты потратил время на дурачка с нейросеткой, вот и будет тебе урок на будущее
предлагаю самостоятельно решить следующую задачу: даны целые неотрицательные a, b, c, научиться находить количество целых неотрицательных решений ax+by=c
исходная задача сводится к этой
Один из способов решения этой задачи - это использование динамического программирования. Мы можем начать с k-го элемента и двигаться назад, вычисляя все возможные значения для каждого элемента. Для каждого элемента fi, мы можем вычислить fi-1 и fi-2 как fk - fk-1 и fk-1 - fk-2 соответственно. Если оба значения неотрицательны, мы продолжаем вычисление для следующего элемента. Если мы достигнем f1 и f2, мы увеличиваем счетчик на 1.
Вот пример кода на C++ для решения этой задачи:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,k;
signed main(){
cin>>t;
while(t--){
cin>>n>>k;
int ans=0;
for(int i=0;i<=n;i++){
int j=n-i,f=1;
for(int l=k;l>=3;l--){
if(i<0||j<0){
f=0;
break;
}
int tmp=i;
i=j-i;
j=tmp;
}
if(f&&i>=0&&j>=0)ans++;
}
cout<<ans<<endl;
}
}
