## 10918 - Tri Tiling

Moderator: Board moderators

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

### an

output one integer number giving the number of possible tilings.

anyway, there is a case N is odd.

Sorry For My Poor English..

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

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

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

Any help appreciated.

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

### Re: 10918 - Tri-Tialing

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

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

### Re: 10918 - Tri-Tialing

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

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
I figured out the DP solution and am happy now

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

### Re: an

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

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
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
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:
Ya, this is usually the case with counting problems..

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

### Re: 10918 - Tri-Tiling

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

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