|Online Judge||Problem Set||Authors||Online Contests||User|
Dragon Slayer Qualification Exam
You might think that Earth is the only planet where life is going on, but it is not true. About 880,228 light years away from Earth, there is a big planet, Haden, where another kind of human beings exists.
Unfortunately, there is another creature living on Haden: a dragon. This dragon attacks villages to find food whenever it gets hungry. People are getting sick of being attacked and being harmed. Now, they decided to select one strong dragon slayer to kill the dragon.
As one of human beings living on Haden, you've seen a lot of disasters caused by the dragon and you want to become a good dragon slayer. Here's the first task that you are given:
You have an n by n chess board where n is even. This chess board looks regular except that it has a couple of red cells and yellow cells, not only black and/or white. You are going to place many of white rooks and/or black rooks on the chess board. Here are the rules:
Let's take a look at following examples.
On the left 6 by 6 chess board, you can place 6 black rooks and 6 white rooks as indicated as small circles. On the right board, it is a bit more complicated due to two red cells, but you can safely place the same number of rooks here, too. Since you can never place more than 2n rooks (n white rooks and n black rooks), this is the maximum number of rooks that you can place without violating any rules. Note that both examples don't have any yellow cells. Let's write a program to solve this task so that you can advance to the next round!
A test set can have several test cases, and the number of test cases is given at the first line. Each test case starts with three integers, n, m, and k where n tells you the size of a chess board, m is the number of red cells on the board, and k is the number of yellow cells. Each of following m lines contains two integers (row number and column number, 0-based), representing a red cell on the board. Then, each of following k lines contains two integers, representing a yellow cell on the board. See the sample input for clarification. You may assume that any cell cannot be both yellow and red and that the same cell is not given more than once. For each test case, n, m, and k do not exceed 40, 10, and 1600, respectively.
For each test case, output only one integer, the maximum possible number of rooks that you can place. If such placement doesn't exist, output 0.
4 6 0 0 6 2 0 2 1 5 5 2 0 2 0 0 0 1 2 3 1 0 0 0 1 1 1 1 0
12 12 2 3
It does not matter whether the left-top cell is black or white in this problem. However, if you want, here is a simple, nice way to determine the color of each cell: Cell (r, c) is white if and only if it is neither yellow nor red and r+c is odd. Cell (r, c) is black if and only if it is neither yellow nor red and r+c is even. Here, (r, c) means that the cell is on the r-th row and on the c-th column.
POJ Monthly--2007.08.05, Hooyeon Lee (ltdtl@POJ), "I like dragons"
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator