Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Dragon Slayer Qualification Exam
Description 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 - Each cell has a color of black, white, yellow, or red
- You cannot place any rooks on yellow cells
- You must place one rook (either black or white, your choice) on each red cell
- You may not place a black rook on a black cell
- You may not place a white rook on a white cell
- There should be no pair of two rooks with the same color that can attack each other. If two rooks with the same color are placed on the same row OR same column, they can attack each other.
- You must maximize the total number of rooks that you place on the board
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 2 Input 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, Output 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.
Sample Input 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 Sample Output 12 12 2 3 Hint 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.Source POJ Monthly--2007.08.05, Hooyeon Lee (ltdtl@POJ), "I like dragons" |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator