Page 1 of 1
an
Posted: Sun Sep 25, 2005 12:14 pm
by wook
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.
Re: 10918(Tri tiling)- i wonder if there are non-even inputs
Posted: Sun Sep 25, 2005 11:03 pm
by Martin Macko
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.
10918 - Tri-Tialing
Posted: Mon Sep 26, 2005 1:50 am
by cypressx
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.
Re: 10918 - Tri-Tialing
Posted: Mon Sep 26, 2005 2:22 am
by Martin Macko
Why have you created another topic on this problem, if there is already one? (
http://online-judge.uva.es/board/viewtopic.php?t=8995)
Re: 10918 - Tri-Tialing
Posted: Mon Sep 26, 2005 2:28 am
by Martin Macko
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.
Posted: Mon Sep 26, 2005 2:51 am
by cypressx
Thank you for your support.
I figured out the DP solution and am happy now
Re: an
Posted: Mon Sep 26, 2005 10:26 am
by TISARKER
What wil be output For the following input set
[b]Input:[/b]
[quote]
0
1
3
5
7
-1
[/quote]
dt
Posted: Mon Sep 26, 2005 11:06 am
by wook
1
0
0
0
0
it is not difficult to guess.
you should have been more careful about it.
Posted: Sat Oct 01, 2005 9:52 pm
by qndel
1
0
0
0
0
i think the answer should be :
0
0
0
0
0
Posted: Sat Oct 01, 2005 10:02 pm
by qndel
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.
Posted: Sat Oct 01, 2005 11:35 pm
by Larry
Ya, this is usually the case with counting problems..
Re: 10918 - Tri-Tiling
Posted: Sat May 20, 2006 11:42 pm
by Martin Macko
IRA wrote:2
4
6
8
10
12
14
16
My AC's output:
Re: 10918 - Tri Tiling
Posted: Mon Mar 28, 2011 7:06 am
by DD
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