491 - Tile Topology

All about problems in Volume 4. 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
Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

491 - Tile Topology

Post by Antonio Ocampo » Sun Jan 30, 2005 6:59 am

Hi, please could someone give me a hint?? I haven't realized which is the pattern :oops:

Thanks in advance :wink:

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 10, 2005 10:28 pm

I don't think there is any known formula for this sequence. You have to either do brute force or cheat and look on Mathworld or the EIS. :-)

Could anyone please tell me what the input format is? Is there just one number? Are there many numbers? What are these numbers separated by?

Also, could anyone say what the answer to the input 10 is? I think it should be 9189, but I'm getting WA.

Thanks.
If only I had as much free time as I did in college...

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Wed May 11, 2005 1:43 am

I don't know what the input format is exactly, but scanf("%d",&n) until EOF works. There are >1 numbers. 9189 is the correct answer for input 10. Maybe your solution misses some corner cases, like 0? (I haven't checked if such input exists, though.)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed May 11, 2005 2:29 am

Thank you. I got it accepted after guessing that the answer for the case 0 is 0, not 1.
If only I had as much free time as I did in college...

plankton
New poster
Posts: 3
Joined: Sun Sep 11, 2005 11:07 pm

Post by plankton » Sun Sep 11, 2005 11:14 pm

Do you know what the input size is??

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Sep 12, 2005 12:05 am

There are no inputs larger than 25.
If only I had as much free time as I did in college...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Sep 12, 2005 12:27 am

All inputs are at most 15.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

491 Tile Topology

Post by IRA » Sun Jan 29, 2006 5:52 am

How to think about the problem?
Does it have any formula about the problem?
Please give me some hint....
Thanks in advance!

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Jan 29, 2006 12:38 pm

I think it a math problem.
And if you want to solve it, you might use DP
Or there are some strange solutions can solve it, like 10918.
I also haven't found out how to solve it.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Sun Jan 29, 2006 5:25 pm

Wei-Ming Chen wrote:I think it a math problem.
And if you want to solve it, you might use DP
Or there are some strange solutions can solve it, like 10918.
I also haven't found out how to solve it.
I solve 10918 to see the page as follow.
http://www.algorithmist.com/index.php/UVa_10918
You can read the page and find the formula.

Solmon K.
New poster
Posts: 34
Joined: Sun Jun 04, 2006 4:57 am
Location: Busan, Korea

....

Post by Solmon K. » Mon Jun 12, 2006 11:43 am

I used brute force and got AC.

See this site:

http://mathworld.wolfram.com/Polyomino.html
Sorry for my bad English...

OTL
frustrate

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Re: 491 Tile Topology

Post by yiuyuho » Fri Apr 24, 2009 11:33 pm

Is there an efficient way to brute force this?

Post Reply

Return to “Volume 4 (400-499)”