I have no idea about the solution.
Can you help me?
10237  Bishops
Moderator: Board moderators

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
hmm...I rotate the board by 45 degrees and then don't know what to do next...Anderson wrote:If you consider the problem ,which is about Root instead of Bishop,
maybe it is easy.
now ,you could rotate the board by 45 degrees , then youn could consider the Bishop like a Root.
Good lucK!!
Can you explain how to use DP to solve this problem?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
You extract from the rotated board all Fields of one colour. For n=4 you have:
Let this figure be B.
You add to this figure points to make a rectangle, the added points are A.
In this example you have a 4x3 rectangle. Imagine you have placed kr rooks on points in A and r rooks on points in B and they are in nonattacking positions. Let A_krB_r be the number of possibilites to place the rooks in this way. If you want to add another rook, you have (nk)*(mk) possibilities. If you placed the rook in figure A, you have (kr+1) identical placements, if you placed it in figure B, there are (r+1). So you have the equation:
(nk)*(mk)*A_krB_r = (kr+1)*A_kr+1B_r+(r+1)*A_krB_r+1
If you know all A_kB_0 and A_0B_1, you can calculate all A_0B_k.
With this equation you can solve the problem, but it is a bit difficult, I needed several hours.
Code: Select all
.
...
...
.
You add to this figure points to make a rectangle, the added points are A.
In this example you have a 4x3 rectangle. Imagine you have placed kr rooks on points in A and r rooks on points in B and they are in nonattacking positions. Let A_krB_r be the number of possibilites to place the rooks in this way. If you want to add another rook, you have (nk)*(mk) possibilities. If you placed the rook in figure A, you have (kr+1) identical placements, if you placed it in figure B, there are (r+1). So you have the equation:
(nk)*(mk)*A_krB_r = (kr+1)*A_kr+1B_r+(r+1)*A_krB_r+1
If you know all A_kB_0 and A_0B_1, you can calculate all A_0B_k.
With this equation you can solve the problem, but it is a bit difficult, I needed several hours.

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
1. Can anybody verify some inputs & outputs?
My long long int program works elegantly for all sample cases, but it resulted in WA. So I inserted a line like
[cpp]assert(sum < (long long)1000 * 1000 * 1000 * 1000 * 1000);[/cpp]
and look! I got SIGABRT at once. And actually my program causes overflow in cases like 30 38..
So I pasted in my VERYVERYslow bigint routine and converted all the procedures (boring work) and got WA in 9.773 sec. I'm confused!
Thanks in advance.
input wrote:10 18
8 5
8 8
8 7
30 38
30 9
30 10
30 0
0 0
2. I'm curious about the judge's limit with the resulting number. Is it true? Did anybody get AC with 64bit integers?output wrote:1024
1444928
22522960
14082528
1459678371142772586080904047004955072918158573568
198564604657832714496
11540432810453797635840
1
My long long int program works elegantly for all sample cases, but it resulted in WA. So I inserted a line like
[cpp]assert(sum < (long long)1000 * 1000 * 1000 * 1000 * 1000);[/cpp]
and look! I got SIGABRT at once. And actually my program causes overflow in cases like 30 38..
So I pasted in my VERYVERYslow bigint routine and converted all the procedures (boring work) and got WA in 9.773 sec. I'm confused!
Thanks in advance.
JongMan @ Yonsei