Code: Select all
f(i) = 4 * f(i - 2) + f(i - 1)
f(i) = 1 if i = 0
f(i) =0 if i < 0
my output for
Code: Select all
4
1
2
3
4
Code: Select all
1
5
9
29
Moderator: Board moderators
Code: Select all
f(i) = 4 * f(i - 2) + f(i - 1)
f(i) = 1 if i = 0
f(i) =0 if i < 0
Code: Select all
4
1
2
3
4
Code: Select all
1
5
9
29
Yes, this is an easy problem. You've missed the following two patterns:saman_saadi wrote: There are four possibilities for selecting one square and one L-shape (4 * f(i - 2)) and there is one possibility for selecting 2 squares (f(i - 1)). Is this approach correct? If not why?
Code: Select all
aab
abb
abb
aab
Code: Select all
f(0)=1
f(1)=1
f(2)=5
Code: Select all
5
39
Code: Select all
87
76546047
I guess there is an error in your recursion. And use long long int type for array. The correct output is:Ron wrote:im getting WA .....
input
my outputCode: Select all
5 39
if my output is wrong........Code: Select all
87 76546047
what should i do in my code....
Code: Select all
65
5307721328585529
Code: Select all
#include <iostream>
using namespace std;
int main(){
unsigned long long fib[41];
fib[0]=1;
fib[1]=1;
fib[2]=5;
for (int i=3;i<=40;i++)
fib[i]=4*fib[i-2]+fib[i-1];
int casos;
cin >> casos;
int j;
for (long caso=0;caso<casos && cin >> j ;caso++){
if (caso!=0) cout << endl;
if (j>=0)
cout << fib[j];
else
cout << "0";
}
return 0;
}
Code: Select all
42
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Code: Select all
0
1
1
5
9
29
65
181
441
1165
2929
7589
19305
49661
126881
325525
833049
2135149
5467345
14007941
35877321
91909085
235418369
603054709
1544728185
3956947021
10135859761
25963647845
66507086889
170361678269
436390025825
1117836738901
2863396842201
7334743797805
18788331166609
48127306357829
123280631024265
315789856455581
808912380552641
2072071806374965
5307721328585529
13596008554085389
Code: Select all
keep dreaming...
thanks to helloneo.helloneo wrote:Are you sure that the test case is less than 1004 ?
You don't need to store all the test inputs..
Just read one line and print output.. and read next line and print output.. and so on..
Code: Select all
Code: Select all
keep dreaming...
Hi! Helloneo. I can't understand why your output is correct....helloneo wrote:Try this input..
Code: Select all
3 3 4 5
My output is..
Hope this help..Code: Select all
11 33 87
Code: Select all
fib[2]=4*fib[0]+fib[1]=4*1+1=5
fib[3]=4*fib[1]+fib[2]=4*1+5=9
fib[4]=4*fib[2]+fib[3]=4*5+9=29
fib[5]=4*fib[3]+fob[4]=4*9+29=65
Code: Select all
fib[3]=11
fib[4]=33
fib[5]=87