codeforces#P2111B. Fibonacci Cubes
-
ID: 37711
Type: RemoteJudge
2000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Fibonacci Cubes
以下题面由 AI 翻译。
题目描述
有 $n$ 个斐波那契立方体，其中第 $i$ 个立方体的边长为 $f_i$，而 $f_i$ 是第 $i$ 个斐波那契数。
在这个问题中，斐波那契数的定义如下：
- $f_1 = 1$
- $f_2 = 2$
- 当 $i > 2$ 时，$f_i = f_{i - 1} + f_{i - 2}$
还有 $m$ 个空盒子，其中第 $i$ 个盒子的宽度为 $w_i$，长度为 $l_i$，高度为 $h_i$。
对于这 $m$ 个盒子中的每一个，你需要判断是否所有的立方体都能装入该盒子。立方体必须按照以下规则放置：
- 立方体只能堆叠在盒子中，且立方体的边必须与盒子的边平行；
- 每个立方体必须放置在盒子的底部或其他立方体的顶部，且放置方式必须确保该立方体下方的所有空间都被填满；
- 较大的立方体不能放置在较小的立方体上方。
输入格式
每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10$，$1 \le m \le 2 \cdot 10^5$）——立方体的数量和空盒子的数量。
每个测试用例的接下来 $m$ 行，每行包含 3 个整数 $w_i$、$l_i$ 和 $h_i$（$1 \le w_i, l_i, h_i \le 150$）——第 $i$ 个盒子的尺寸。
输入的额外约束：
- 所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个长度为 $m$ 的字符串，其中第 $i$ 个字符等于 "1" 表示所有 $n$ 个立方体能装入第 $i$ 个盒子，否则为 "0"。
样例数据
2
5 4
3 1 2
10 10 10
9 8 13
14 7 20
2 6
3 3 3
1 2 1
2 1 2
3 2 2
2 3 1
3 2 4
0010
100101
提示
在第一个测试用例中，只有一个盒子是合适的。立方体可以如下放置：
