![:o](./images/smilies/icon_eek.gif)
10694 - Combinatorial Summation
Moderator: Board moderators
Nice Problem of Fibonacci
The difference increases at a fibonacci number rate (I may forget). But, Definitely a very good problem from sajjad bhai.
Anupam![:lol:](./images/smilies/icon_lol.gif)
Anupam
![:lol:](./images/smilies/icon_lol.gif)
"Everything should be made simple, but not always simpler"
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
My solution calculates all answers with dp at the beginning of my program.
Here a pattern can be observed in the differences of adjacent entries in the table (like mentioned before by Larry, similar to fibonacci numbers). So to fill up the table, only a constant number of bigint operations for each entry is necessary.
But I would be interested in how to solve this problem in another way. I do this pattern guessing far too often without knowing for sure why it works.![:(](./images/smilies/icon_frown.gif)
Here a pattern can be observed in the differences of adjacent entries in the table (like mentioned before by Larry, similar to fibonacci numbers). So to fill up the table, only a constant number of bigint operations for each entry is necessary.
But I would be interested in how to solve this problem in another way. I do this pattern guessing far too often without knowing for sure why it works.
![:(](./images/smilies/icon_frown.gif)
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
where is the problem
i got wa
problem description says input will less than 999
why you try with input 1000
help me
i got wa
Code: Select all
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define max 220
#define l 1000
char *add(char *nm1,char *nm2)
{
char res[max];
int i,j,k,op=0,len1,len2;
len1=strlen(nm1);
len2=strlen(nm2);
if(len2>len1)
return add(nm2,nm1);
k=len1+1;
res[k--]='\0';
for(i=len2-1,j=len1-1;i>=0;i--,j--){
op = nm2[i]-'0'+nm1[j]-'0'+op;
res[k--]= (op%10)+'0';
op=op/10;
}
for(;j>=0;j--){
op=nm1[j]-'0'+op;
res[k--]=(op%10)+'0';
op=op/10;
}
if(op){
res[k]=op+'0';
return res;
}
return &res[1];
}
int main (void)
{
char seq[l][max], *p;
int i,n, num;
char one[]={"1"};
//strcpy(seq[0],"0");
strcpy(seq[1],"1");
strcpy(seq[2],"2");
for(i=3;i<l;i++){
p=add(seq[i-1],seq[i-2]);
p=add(p,"1");
strcpy(seq[i],p);
}
cin>>num;
while(num--){
cin>>n;
if(n<1)cout<<"0"<<endl;
else
cout<<seq[n]<<endl;
}
return 0;
}
why you try with input 1000
help me