← 返回题目列表

Codeforces · 2195/F

F. 抛物线独立性

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

给你一套 $$$n$$$ 二次 函数 $$$F=\{f_1,f_2,\ldots,f_n \}$$$,其中 $$$f_i(x)=a_i x^2 + b_i x + c_i$$$。

调用了两个函数 $$$f$$$ 和 $$$g$$$ 独立 如果 $$$f(x) \neq g(x)$$$ 对于所有 $$$x \in \mathbb{R}$$$。

另外,调用了一组函数 $$$G=\{g_1,g_2,\ldots,g_k\}$$$ 组织 如果两个函数 $$$g_i$$$ 和 $$$g_j$$$ 对于所有 $$$1 \le i \lt j \le |G|$$$ 都是独立的。

对于每个 $$$i=1,2,\ldots,n$$$,请找到包含 $$$f_i$$$ 作为元素的 $$$F$$$ 的最大组织子集的大小。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3000$$$)。

接下来的 $$$n$$$ 行包含三个整数 $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ 表示函数 $$$f_i$$$ ($$$-10^6 \le a_i, b_i, c_i \le 10^6$$$, $$$a_i \neq 0$$$)。

保证一个测试用例中的函数是两两不同的。

保证所有测试用例的$$$n^2$$$总和不超过$$$3000^2$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$s_1,s_2,\ldots,s_n$$$,其中 $$$s_i$$$ 是包含 $$$f_i$$$ 的最大组织子集的大小。

示例

输入
复制

3
4
1 2 -1
-3 0 -3
-1 4 -5
1 2 -4
5
3 0 0
1 0 -5
-3 0 0
-1 0 10
1 0 -10
5
884 -667 497
680 -973 213
23 -548 -412
826 359 -333
773 212 218

输出
复制

3 2 3 3
3 3 2 2 3
3 3 3 1 2

注意

第一个测试用例中,功能如下:

  • $$$f_1(x)=x^2+2x-1$$$;
  • $$$f_2(x)=-3x^2-3$$$;
  • $$$f_3(x)=-x^2+4x-5$$$;
  • $$$f_4(x)=x^2+2x-4$$$。

函数图如下所示:

包含每个函数的 $$$F$$$ 的最大组织子集如下:

  • $$$\{f_1,f_3,f_4\}$$$ 是包含 $$$f_1$$$ 的最大组织子集;
  • $$$\{f_1,f_2\}$$$ 是包含 $$$f_2$$$ 的最大组织子集;
  • $$$\{f_1,f_3,f_4\}$$$ 是包含 $$$f_3$$$ 的最大组织子集;
  • $$$\{f_1,f_3,f_4\}$$$ 是包含 $$$f_4$$$ 的最大组织子集。