11310 - Delivery Debacle

[saman_saadi]

This problem was the easiest one and many people solve it in the contest time But I don't know why I can't solve it! I use dp: suppose f(i) is the number of 2-by-i box (width = 2 and length = i) so we have:

Code: Select all

f(i) = 4 * f(i - 2) + f(i - 1)
f(i) = 1 if i = 0
f(i) =0 if i < 0

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?
my output for

Code: Select all

4
1
2
3
4

is

Code: Select all

1
5
9
29

[Robert Gerbicz]

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?

Yes, this is an easy problem. You've missed the following two patterns:

Code: Select all

aab
abb

abb
aab

And use the known values for recursion:

Code: Select all

f(0)=1
f(1)=1
f(2)=5

[saman_saadi]

Thanks Robert Gerbicz. I got AC. It's too bad that I couldn't consider this case Thanks again.

[Ron]

im getting WA .....

input

Code: Select all

5
39

my output

Code: Select all

87
76546047

if my output is wrong........
what should i do in my code....

[Robert Gerbicz]

im getting WA .....

input

Code: Select all

5
39

my output

Code: Select all

87
76546047

if my output is wrong........
what should i do in my code....

I guess there is an error in your recursion. And use long long int type for array. The correct output is:

Code: Select all

65
5307721328585529

The posted input is also wrong. Check out the problem statement:
"The input begins with t, the number of different box lengths."

[apurba]

11310

[sohel]

Do you get the correct output for the input posted above?

[Saul Hidalgo]

Hi! How are all. I got WA in this exercise, and... i proof printing a "\n" in the final, and without thist "\n", and continue WA . Somebody know why thist code have WA.

Here is my code

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;
}

And with this test cases of input

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

My programa have a output:

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

Very thanks for your help.

[helloneo]

Try this input..

Code: Select all

3
3
4
5

My output is..

Code: Select all

11
33
87

Hope this help..

[apurba]

why i am getting RE??????
help pls.
here is my code................

Code: Select all

someone help.

[helloneo]

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..

[apurba]

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..

thanks to helloneo.
but i am getting WA now.......
here is my updated code.....

Code: Select all

strange!!!!!!!!!

[rio]

Because your formula is wrong. Try to get the correct output with helloneo's io test.

-----
Rio

[Saul Hidalgo]

Try this input..

Code: Select all

3
3
4
5

My output is..

Code: Select all

11
33
87

Hope this help..

Hi! Helloneo. I can't understand why your output is correct....
fib[0]=1;
fib[1]=1;
fib=4*fib[i-2]+fib[i-1];

Then, for the fib[2]

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

I can't undestand why your input is:

Code: Select all

fib[3]=11
fib[4]=33
fib[5]=87

[rio]

Read the first and second post of this thread.
I think you are doing the same mistake as saman_saadi did.

-----
Rio