codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1584B.md (1820B)


      1 Source: https://codeforces.com/problemset/problem/1584/B
      2 
      3 B. Coloring Rectangles
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 David was given a red checkered rectangle of size $n \times m$. But he doesn't like it. So David cuts the original or any other rectangle piece obtained during the cutting into two new pieces along the grid lines. He can do this operation as many times as he wants.
     22 
     23 As a result, he will get a set of rectangles. Rectangles $1 \times 1$ are forbidden.
     24 
     25 David also knows how to paint the cells blue. He wants each rectangle from the resulting set of pieces to be colored such that any pair of adjacent cells by side (from the same piece) have different colors.
     26 
     27 What is the minimum number of cells David will have to paint?
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The next lines contain descriptions of test cases.
     32 
     33 The only line of each test case contains two integers $n$, $m$ ($1 \leq n, m \leq 3 \cdot 10^4$, $n \cdot m \geq 2$).
     34 
     35 Output
     36 
     37 For each test case print a single integer — the minimum number of cells David will have to paint blue.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 1 3
     46 2 2
     47 2 5
     48 3 5
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 1
     55 2
     56 4
     57 5
     58 ```
     59 
     60 Note
     61 
     62 The following pictures show how the initial rectangle can be split and cells colored blue.
     63 
     64 In the first test case:
     65 
     66  ![](https://espresso.codeforces.com/d7f5d749e9dc65bd3e86fb1061504752ba2d7d2b.png) 
     67 
     68 In the second test case:
     69 
     70  ![](https://espresso.codeforces.com/ee7607269fa0867cd41d5b715444d7e3fffde8de.png) 
     71 
     72 In the third test case:
     73 
     74  ![](https://espresso.codeforces.com/e6ebbc36c039854851104a1e0a426710825c2a7c.png) 
     75 
     76 In the fourth test case:
     77 
     78  ![](https://espresso.codeforces.com/d23a2d8ccaf8f103aebe6c45de134a204ee23c38.png)