OJ Board

Posted: **Sat Oct 06, 2007 10:03 pm**

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

is

Code: Select all

Posted: **Sat Oct 06, 2007 10:34 pm**

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?

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

Posted: **Sat Oct 06, 2007 10:58 pm**

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

Thanks again.

Posted: **Mon Dec 31, 2007 3:17 pm**

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

Posted: **Mon Dec 31, 2007 4:25 pm**

Ron wrote: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."

Posted: **Fri Jan 04, 2008 12:58 pm**

11310

Posted: **Fri Jan 04, 2008 2:34 pm**

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

Posted: **Fri Jan 04, 2008 2:53 pm**

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

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.

Posted: **Fri Jan 04, 2008 5:19 pm**

Try this input..

Code: Select all

My output is..

Code: Select all

11
33
87

Hope this help..

Posted: **Fri Jan 04, 2008 5:26 pm**

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

Code: Select all




someone help.

Posted: **Fri Jan 04, 2008 6:07 pm**

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

Posted: **Fri Jan 04, 2008 6:49 pm**

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

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

Code: Select all

strange!!!!!!!!!

Posted: **Fri Jan 04, 2008 7:18 pm**

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

-----
Rio

Posted: **Sat Jan 05, 2008 4:42 am**

helloneo wrote: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

Posted: **Sat Jan 05, 2008 4:47 am**

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

-----
Rio

OJ Board

11310 - Delivery Debacle

11310 - Delivery Debacle

Re: 11310 - Delivery Debacle

11310

RE

WA