← 返回题目列表

Codeforces · 2111/B

B. 斐波那契立方体

中文机器翻译题面 查看原题

有 $$$n$$$ 斐波那契立方体,其中第 $$$i$$$ 个立方体的边等于 $$$f_{i}$$$,其中 $$$f_{i}$$$ 是第 $$$i$$$ 个斐波那契数。

在这个问题中,斐波那契数的定义如下:

  • $$$f_{1} = 1$$$
  • $$$f_{2} = 2$$$
  • $$$f_{i} = f_{i - 1} + f_{i - 2}$$$ for $$$i \gt 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$$$ 个盒子中;否则,第 $$$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

注意

在第一个测试用例中,只有一个盒子适合。立方体可以如下放置在其中: