codeforces-scrape

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

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 ![](https://espresso.codeforces.com/2a61db77c7f4e2f142f0a750285355bacf8c4aa3.png)
     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 ![](https://espresso.codeforces.com/5bbfc9fe800c1e2c754d762eb40c9014c3255999.png)