11310 - Delivery Debacle

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11310 - Delivery Debacle

Post by saman_saadi » 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

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

Post by Robert Gerbicz » 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

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

Post by saman_saadi » Sat Oct 06, 2007 10:58 pm

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

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Post by Ron » 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....

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » 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."

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

11310

Post by apurba » Fri Jan 04, 2008 12:58 pm

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

Code: Select all

keep dreaming...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Fri Jan 04, 2008 2:34 pm

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

Post by Saul Hidalgo » 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

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

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

Post by helloneo » Fri Jan 04, 2008 5:19 pm

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

Post by apurba » Fri Jan 04, 2008 5:26 pm

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

Post by helloneo » 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.. :-)

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

WA

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

Code: Select all

keep dreaming...

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

Post by rio » Fri Jan 04, 2008 7:18 pm

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

Post by Saul Hidalgo » 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

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

Post by rio » 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

Post Reply

Return to “Volume 113 (11300-11399)”