2216B.md (1769B)
1 Source: https://codeforces.com/problemset/problem/2216/B 2 3 B. THU Packing Puzzle 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 There are three types of 2D blocks: T-shaped, H-shaped, and U-shaped. Their exact shapes are shown in the figure below: 22 23  24 25 You are given three non-negative integers $c_T$, $c_H$, and $c_U$, representing the numbers of T-shaped, H-shaped, and U-shaped blocks, respectively. Your task is to pack all $(c_T + c_H + c_U)$ blocks into an $n \times 3$ grid, following these rules: 26 27 * Every block must be placed entirely inside the grid; 28 * No two blocks may overlap (i.e., no unit cell can be covered by more than one block); 29 * Blocks can be rotated by any multiple of $90^{\circ}$, but their edges must remain parallel to the grid borders. 30 31 You have to find the minimum possible value of $n$ for which such a packing exists. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The only line of each test case contains three integers $c_T$, $c_H$, and $c_U$ ($0\le c_T,c_H,c_U\le 10^9$, $c_T+c_H+c_U \gt 0$) — the numbers of T-shaped, H-shaped, and U-shaped blocks, respectively. 38 39 Output 40 41 For each test case, output a single integer — the minimum possible value of $n$. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 1 1 1 51 52 2 0 0 53 54 1 1 0 55 56 0 0 1000000000 57 58 1000000000 1000000000 1000000000 59 ``` 60 61 Output 62 63 ``` 64 7 65 66 5 67 68 5 69 70 3000000000 71 72 7000000000 73 ``` 74 75 Note 76 77 The optimal solutions for the first three test cases are listed below: 78 79 