## 11006 - Wheel Good

Moderator: Board moderators

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

### 11006 - Wheel Good

I am getting WA for this problem. Not very surprising since I just follow my intuition to code it.

I get a 7592-gon for N = 100000. Is this correct? If not, could anyone please give any hints? Thank you.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Oops. I see some flaws in my idea. I shall post more after I have fixed that.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Accepted. The number above should be correct. Also, for N = 13, you should get a 20-gon.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.
Can you give me a hint or small input/output for this problem?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
a similar TopCoder problem:
http://www.topcoder.com/stat?c=problem_ ... 87&rd=8068

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
aminallam wrote:Can you give me a hint or small input/output for this problem?
Hint: greedy.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.
Thank you very much Mr. Misof. It is nice to see you here. Thanks Mr. tobby.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.
For Mr. tobby, if you have time, please describe the greedy approach.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Maybe you should try to construct by hand a 20-gon for N=13 to begin with. Sorry I don't have time now to explain more. Will write more later if I have time.

Note that the polygon you get need not be mirror symmetric.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Why is the problem statement written in that style..
.. isn't it kind of confusing.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
tobby wrote: Hint: greedy.
I don't have any thought how to greedy.
Could you give more hints?

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I promised to leave some hints here, so I am back!

Think about a highly related problem: how do you construct the smallest 4k-gon (in terms of its width) satisfying the symmetry property?

Code: Select all

``````   k = 1      k = 2      k = 3

_          _
|_|        / \
|   |        ?
\_/

width = 1  width = 3  width = ?``````