## 11310 - Delivery Debacle

Moderator: Board moderators

New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

### 11310 - Delivery Debacle

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11310 - Delivery Debacle

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

New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran
Thanks Robert Gerbicz. I got AC. It's too bad that I couldn't consider this case Thanks again.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA
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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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."

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### 11310

11310
Last edited by apurba on Fri Jan 04, 2008 5:12 pm, edited 1 time in total.

Code: Select all

``keep dreaming...``

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Do you get the correct output for the input posted above?

Saul Hidalgo
New poster
Posts: 18
Joined: Wed Jan 03, 2007 2:36 am
Location: Los Teques, Venezuela
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``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Try this input..

Code: Select all

``````3
3
4
5``````

My output is..

Code: Select all

``````11
33
87``````
Hope this help..

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### RE

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

Code: Select all

``````

someone help.``````
Last edited by apurba on Fri Jan 04, 2008 6:46 pm, edited 1 time in total.

Code: Select all

``keep dreaming...``

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### WA

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!!!!!!!!!
Last edited by apurba on Fri Jan 04, 2008 7:42 pm, edited 1 time in total.

Code: Select all

``keep dreaming...``

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Because your formula is wrong. Try to get the correct output with helloneo's io test.

-----
Rio

Saul Hidalgo
New poster
Posts: 18
Joined: Wed Jan 03, 2007 2:36 am
Location: Los Teques, Venezuela
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``````

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan