Problem Description
Chef's team is going to participate at the legendary math battles. One of the main task in the competition is to calculate the number of ways to create a number by adding some Chefonacci numbers. A number is called a Chefonacci number if it is an element of Chefonacci sequence defined as follows.
f(0) = 1;
f(1) = 2;
For i > 1 : f(i) = f(i - 1) + f(i - 2)
Chef asked you to help him with this task. There will be Q question of form X, K : How many different ways are there to create X by adding K Chefonacci numbers. Note that the order of numbers in the addition does not matter, i.e. (f(i) + f(j) + f(k)) and (f(j) + f(i) + f(k)) will not be counted as distinct ways. Also note that you are allowed to use a Chefonacci number any number of times (zero or more).
As the answer could be large, print your answer modulo 109 + 7 (1000000007)CODING ARENA
#include<stdio.h>
int main()
{
int a,b,c,q,x,k,i,ans,temp,j,j2,j3,j4,j5,j6,j7,j8,j9,n;
int arr[50];
int flag=1;
a=1;
b=2;
i=1;
arr[0]=1;
while(b<1000000000)
{
arr[i]=b;
i++;
c=b;
b+=a;
a=c;
}
scanf("%d",&q);
while(q--)
{
scanf("%d %d",&x,&k);
ans=0;
n=43;
flag=1;
if(k==1)
{
for(i=0;i<n&&flag;i++)
{
if(arr[i]==x)
{
ans=1;
break;
}
else if(arr[i]>x)
{
break;
}
}
}
else if(k==2)
{
for(i=0;i<n&&flag;i++)
{
for(j=i;j<n&&flag;j++)
{
if(arr[i]+arr[j]==x)
{
ans++;
}
else if(arr[i]+arr[j]>x)
{
break;
}
}
}
}
else if(k==3)
{
for(i=0;i<n&&flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
temp=arr[i]+arr[j]+arr[j2];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
}
}
}
else if(k==4)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
}
}
}
}
else if(k==5)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
for(j4=j3;j4<n && flag;j4++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3]+arr[j4];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
}
}
}
}
}
else if(k==6)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
for(j4=j3;j4<n && flag;j4++)
{
for(j5=j4;j5<n;j5++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3]+arr[j4]+arr[j5];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
}
else if(k==7)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
for(j4=j3;j4<n && flag;j4++)
{
for(j5=j4;j5<n;j5++)
{
for(j6=j5;j6<n;j6++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3]+arr[j4]+arr[j5]+arr[j6];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
}
else if(k==8)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
for(j4=j3;j4<n && flag;j4++)
{
for(j5=j4;j5<n;j5++)
{
for(j6=j5;j6<n;j6++)
{
for(j7=j6;j7<n;j7++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3]+arr[j4]+arr[j5]+arr[j6]+arr[j7];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
}
else if(k==9)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
for(j4=j3;j4<n && flag;j4++)
{
for(j5=j4;j5<n;j5++)
{
for(j6=j5;j6<n;j6++)
{
for(j7=j6;j7<n;j7++)
{
for(j8=j7;j8<n;j8++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3]+arr[j4]+arr[j5]+arr[j6]+arr[j7]+arr[j8];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
}
else if(k==10)
{
for(i=0;i<n && flag;i++)
{
for(j=i;j<n && flag;j++)
{
for(j2=j;j2<n && flag;j2++)
{
for(j3=j2;j3<n && flag;j3++)
{
for(j4=j3;j4<n && flag;j4++)
{
for(j5=j4;j5<n;j5++)
{
for(j6=j5;j6<n;j6++)
{
for(j7=j6;j7<n;j7++)
{
for(j8=j7;j8<n;j8++)
{
for(j9=j8;j9<n;j9++)
{
temp=arr[i]+arr[j]+arr[j2]+arr[j3]+arr[j4]+arr[j5]+arr[j6]+arr[j7]+arr[j8]+arr[j9];
if(temp==x)
{
ans++;
}
else if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
if(temp>x)
{
break;
}
}
}
printf("%d\n",ans);
}
return 0;
}
Test Case 1
Input (stdin)5 12 1 13 1 13 2 13 3 13 4
Expected Output0 1 1 2 4
Test Case 2
Input (stdin)5 12 1 14 1 13 2 11 0 15 4
Expected Output0 0 1 0 4
No comments:
Post a Comment