10918 - Tri Tiling

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

Moderator: Board moderators

Post Reply
wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

an

Post by wook » Sun Sep 25, 2005 12:14 pm

our task is

output one integer number giving the number of possible tilings.

anyway, there is a case N is odd.

think more cafefully about it.
Sorry For My Poor English.. :)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10918(Tri tiling)- i wonder if there are non-even inputs

Post by Martin Macko » Sun Sep 25, 2005 11:03 pm

boulder wrote:why can't i suppose that the tiling with more than one holes (i.e. with 2 or more holes) could also be correct? So what is the meaning of the task then?
There mustn't be any holes in the tiling.

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

10918 - Tri-Tialing

Post by cypressx » Mon Sep 26, 2005 1:50 am

Hello , I cannot figure out the solution , and when the problem is considered as an easy one I am getting little frustrated ( there probably is something very little which I can't see ) :( Please help me to get out of this situation. This is the solution I coded , but it appears to be wrong. I don't know why ? It is missing some case I guess :

int ans[maxn];
ans[0] = 1;
ans[2] = 3;
for(int i=4;i<=30;i+=2) {
ans = 3 * ans[i-2];
if(i%4==0) ans += (i/4)*ans[i-4];
else if(i%4==2) ans += (i/4)*ans[i-4]*3;
}

Please give me some hint.
Any help appreciated.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10918 - Tri-Tialing

Post by Martin Macko » Mon Sep 26, 2005 2:22 am

Why have you created another topic on this problem, if there is already one? (http://online-judge.uva.es/board/viewtopic.php?t=8995)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10918 - Tri-Tialing

Post by Martin Macko » Mon Sep 26, 2005 2:28 am

cypressx wrote:Hello , I cannot figure out the solution , and when the problem is considered as an easy one I am getting little frustrated ( there probably is something very little which I can't see ) :( Please help me to get out of this situation. This is the solution I coded , but it appears to be wrong. I don't know why ? It is missing some case I guess :

int ans[maxn];
ans[0] = 1;
ans[2] = 3;
for(int i=4;i<=30;i+=2) {
ans = 3 * ans[i-2];
if(i%4==0) ans += (i/4)*ans[i-4];
else if(i%4==2) ans += (i/4)*ans[i-4]*3;
}

Please give me some hint.
Any help appreciated.

Accorting to the code you've posted:
ans[4]=3*ans[2]+(4/4)*ans[0]=3*3+1*1=10.

But there are 11 different tilings for N=4.

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx » Mon Sep 26, 2005 2:51 am

Thank you for your support.
I figured out the DP solution and am happy now :D

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Re: an

Post by TISARKER » Mon Sep 26, 2005 10:26 am

What wil be output For the following input set
[b]Input:[/b]
[quote]
0
1
3
5
7
-1
[/quote]
Mr. Arithmetic logic Unit

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

dt

Post by wook » Mon Sep 26, 2005 11:06 am

1
0
0
0
0
it is not difficult to guess.
you should have been more careful about it.
Sorry For My Poor English.. :)

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

Post by qndel » Sat Oct 01, 2005 9:52 pm

1
0
0
0
0
i think the answer should be :
0
0
0
0
0
NOthing special

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

Post by qndel » Sat Oct 01, 2005 10:02 pm

Very strange think, before I submit my program i thought that for n=0 answer is 0 but now i see that if you want to have ACC you should return 1 for n=0. All in All i think that there is a mistake in a test files.
NOthing special

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Oct 01, 2005 11:35 pm

Ya, this is usually the case with counting problems..

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10918 - Tri-Tiling

Post by Martin Macko » Sat May 20, 2006 11:42 pm

IRA wrote:2
4
6
8
10
12
14
16
My AC's output:

Code: Select all

3
11
41
153
571
2131
7953
29681

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10918 - Tri Tiling

Post by DD » Mon Mar 28, 2011 7:06 am

qndel wrote:Very strange think, before I submit my program i thought that for n=0 answer is 0 but now i see that if you want to have ACC you should return 1 for n=0. All in All i think that there is a mistake in a test files.
I think it is because that the only one way is to put no domino :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 109 (10900-10999)”