### 10237 - Bishops

Posted:

**Sat Apr 27, 2002 9:29 pm**I have no idea about the solution.

Can you help me?

Can you help me?

Page **1** of **1**

Posted: **Sat Apr 27, 2002 9:29 pm**

I have no idea about the solution.

Can you help me?

Can you help me?

Posted: **Tue May 28, 2002 3:18 pm**

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!!

maybe it is easy.

now ,you could rotate the board by 45 degrees , then youn could consider the Bishop like a Root.

Good lucK!!

Posted: **Sun Jul 21, 2002 6:24 pm**

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?

Posted: **Tue Jul 23, 2002 11:18 pm**

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.

Posted: **Sat Dec 27, 2003 4:46 pm**

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. 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.

Posted: **Tue Dec 30, 2003 1:34 pm**

Yes, long long is sufficient to get AC.

Your I/O are correct (though my program overflows on the three big ones, so I don't know about those), but I see you have no odd n among them, so you could try the input "5 5" which should give "3368".

Your I/O are correct (though my program overflows on the three big ones, so I don't know about those), but I see you have no odd n among them, so you could try the input "5 5" which should give "3368".

Posted: **Wed Dec 31, 2003 3:16 am**

Hi, Per!

After correcting a SILLY SILLY VERY SILLY mistake in the size of the array, my program got AC. How silly I was

Thank you very much, again.

Happy new year! Looking forward to see you in Prague!

After correcting a SILLY SILLY VERY SILLY mistake in the size of the array, my program got AC. How silly I was

Thank you very much, again.

Happy new year! Looking forward to see you in Prague!

Posted: **Thu Nov 08, 2007 4:01 am**

Anybody can explain Adrian's message?

I tried, but I dont understand his variables...

I tried, but I dont understand his variables...