10918 - Tri Tiling

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

Martin Macko · 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 · 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.

Martin Macko · 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)

Martin Macko · 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 · 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

TISARKER · 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]

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

qndel · 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

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

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

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

Martin Macko · 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

DD · 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

OJ Board

10918 - Tri Tiling

an

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

10918 - Tri-Tialing

Re: 10918 - Tri-Tialing

Re: 10918 - Tri-Tialing

Re: an

dt

Re: 10918 - Tri-Tiling

Re: 10918 - Tri Tiling