## 491 - Tile Topology

Moderator: Board moderators

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 491 - Tile Topology

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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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:
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.)

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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
Do you know what the input size is??

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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:
All inputs are at most 15.

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

### 491 Tile Topology

How to think about the problem?
Does it have any formula about the problem?

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
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
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

### ....

I used brute force and got AC.

See this site:

http://mathworld.wolfram.com/Polyomino.html

OTL
frustrate

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

### Re: 491 Tile Topology

Is there an efficient way to brute force this?