codeforces-scrape

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

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  ![](https://espresso.codeforces.com/340ee01a170541f7d4b306492d48982aeeb3e49f.png)