2111B.md (2234B)
1 Source: https://codeforces.com/problemset/problem/2111/B 2 3 B. Fibonacci Cubes 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There are $n$ Fibonacci cubes, where the side of the $i$-th cube is equal to $f_{i}$, where $f_{i}$ is the $i$-th Fibonacci number. 22 23 In this problem, the Fibonacci numbers are defined as follows: 24 25 * $f_{1} = 1$ 26 * $f_{2} = 2$ 27 * $f_{i} = f_{i - 1} + f_{i - 2}$ for $i \gt 2$ 28 29 There are also $m$ empty boxes, where the $i$-th box has a width of $w_{i}$, a length of $l_{i}$, and a height of $h_{i}$. 30 31 For each of the $m$ boxes, you need to determine whether all the cubes can fit inside that box. The cubes must be placed in the box following these rules: 32 33 * The cubes can only be stacked in the box such that the sides of the cubes are parallel to the sides of the box; 34 * Every cube must be placed either on the bottom of the box or on top of other cubes in such a way that all space below the cube is occupied; 35 * A larger cube cannot be placed on top of a smaller cube. 36 37 Input 38 39 Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^{3}$) — the number of test cases. The description of the test cases follows. 40 41 In the first line of each test case, there are two integers $n$ and $m$ ($2 \le n \le 10, 1 \le m \le 2 \cdot 10^{5}$) — the number of cubes and the number of empty boxes. 42 43 The next $m$ lines of each test case contain $3$ integers $w_{i}$, $l_{i}$, and $h_{i}$ ($1 \le w_{i}, l_{i}, h_{i} \le 150$) — the dimensions of the $i$-th box. 44 45 Additional constraints on the input: 46 47 * The sum of $m$ across all test cases does not exceed $2 \cdot 10^{5}$. 48 49 Output 50 51 For each test case, output a string of length $m$, where the $i$-th character is equal to "1" if all $n$ cubes can fit into the $i$-th box; otherwise, the $i$-th character is equal to "0". 52 53 Example 54 55 Input 56 57 ``` 58 2 59 60 5 4 61 62 3 1 2 63 64 10 10 10 65 66 9 8 13 67 68 14 7 20 69 70 2 6 71 72 3 3 3 73 74 1 2 1 75 76 2 1 2 77 78 3 2 2 79 80 2 3 1 81 82 3 2 4 83 ``` 84 85 Output 86 87 ``` 88 0010 89 100101 90 ``` 91 92 Note 93 94 In the first test case, only one box is suitable. The cubes can be placed in it as follows: 95 96 