#include <iostream>
using namespace std;
int main()
{
int i,n,tap=1,tp=2,tc;
cin>>n;
for(i=3;i<=n;i++)
{
tc=tap+tp;
tap=tp
;
tp=tc;
}
if(n<=2)
cout<<n;
else
cout<<tc;
}
Spanul cel din urma
#include <iostream>
using namespace std;
int v[100001],n,k;
int main()
{
int i;
cin>>n>>k;
v[1]=v[2]=1;
for(i=3;i<=k+1;i++)
v[i]=v[i-1]*2%9001;
for(i=k+2;i<=n;i++)
v[i]=(2*v[i-1]-v[i-k-1]+9001)%9001;
cout<<v[n];
}