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 k-r rooks on points in A and r rooks on points in B and they are in nonattacking positions. Let A_k-rB_r be the number of possibilites to place the rooks in this way. If you want to add another rook, you have (n-k)*(m-k) possibilities. If you placed the rook in figure A, you have (k-r+1) identical placements, if you placed it in figure B, there are (r+1). So you have the equation:
(n-k)*(m-k)*A_k-rB_r = (k-r+1)*A_k-r+1B_r+(r+1)*A_k-rB_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 k-r rooks on points in A and r rooks on points in B and they are in nonattacking positions. Let A_k-rB_r be the number of possibilites to place the rooks in this way. If you want to add another rook, you have (n-k)*(m-k) possibilities. If you placed the rook in figure A, you have (k-r+1) identical placements, if you placed it in figure B, there are (r+1). So you have the equation:
(n-k)*(m-k)*A_k-rB_r = (k-r+1)*A_k-r+1B_r+(r+1)*A_k-rB_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 VERY-VERY-slow 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.

So I pasted in my VERY-VERY-slow bigint routine and converted all the procedures (boring work) and got WA in 9.773 sec.

Thanks in advance.

JongMan @ Yonsei