题目内容

在一个气象观测站中，每条观测记录包含多个数值指标和一个二元类别标记（0 或 1）。现在需要只选择一个指标和一个分界值，构造一条最简单的判定规则：若该指标值不超过分界值，则归入左组；否则归入右组。左组和右组各给出一个固定的预测类别。

设一个组中类别 0 的数量为 $a$，类别 1 的数量为 $b$，则该组的混杂度定义为 $H=1-\left(\frac{a}{a+b}\right)^2-\left(\frac{b}{a+b}\right)^2$；若组为空，混杂度为 0。

训练时，设训练样本总数为 $n$，指标数为 $m$。对每个指标 $j$（下标从 0 开始）执行以下步骤：按该指标值稳定升序排列；若指标值相同，保持训练数据中的原顺序。候选分界值包括每一对相邻且不相等的指标值的中点，以及最小指标值减去 $\varepsilon$，其中 $\varepsilon=1\times10^{-7}$。对每个候选分界值，将排列后位于分界值之前的样本作为左组，之后的样本作为右组；若某一侧为空，则丢弃该候选分界值。

对左组和右组分别计算混杂度，并计算加权混杂度 $Q=\frac{n_L}{n}H_L+\frac{n_R}{n}H_R$，其中 $n_L,n_R$ 分别为左、右组样本数。该指标的最优分界值是使 $Q$ 最小的候选分界值；若并列，取分界值最小者。

在所有指标中，取使 $Q$ 最小的指标和分界值；若并列，先取指标下标较小者，再取分界值较小者。最优指标对应的左组和右组预测类别分别为各组中出现次数更多的类别标记；若组内两个类别数量相同，则预测 0。

如果没有任何可行的候选分界值，则使用整个训练集中出现次数更多的类别标记作为默认预测；若数量相同，则默认预测 0。

预测时，对每条测试样本，如果最优指标值 $\le$ 分界值，则输出左组预测类别，否则输出右组预测类别；若使用默认预测，则所有测试样本均输出默认预测。

训练样本数 $n$ 至少为 2，指标数 $m$ 至少为 1，测试样本数 $k$ 至少为 1。所有数值均为整数或浮点数且无缺失值。

输入描述

标准输入仅包含一行，为一个 JSON 对象，包含两个字段：

• train：二维数组，表示训练数据。train 中每个元素是一个一维数组，前 $m$ 个值为数值指标，最后一个值为类别标记（0 或 1）。
• test：二维数组，表示测试数据。test 中每个元素是一个一维数组，包含 $m$ 个数值指标。 保证训练样本数至少为 2，指标数至少为 1，测试样本数至少为 1。所有元素均为整数或浮点数且无缺失值。

输出描述

输出一行，一个 JSON 数组，按 test 中样本的输入顺序给出每个测试样本的预测类别，每个元素为 0 或 1。

样例1

输入

{"train": [[1, 5, 0], [2, 6, 0], [3, 7, 1]], "test": [[1, 5], [2, 6], [2.5, 6.5], [3, 7]]}

输出

[0, 0, 0, 1]

说明

训练集有 2 个指标，样本数 n = 3。

指标 0 的取值为 1, 2, 3。候选分界值 1.5 的加权混杂度 $Q=\frac{1}{3}$；候选分界值 2.5 左侧为 [0, 0]、右侧为 [1]，两组混杂度都为 0，所以 $Q=0$。

指标 1 的取值为 5, 6, 7，候选分界值 6.5 同样得到 $Q=0$。两个指标并列最优，根据规则先取指标下标较小的 0，因此最优分界值为 2.5。

左组预测类别为 0，右组预测类别为 1。测试样本在指标 0 上的值 1、2、2.5 均不大于 2.5，输出 0；3 > 2.5 输出 1。

样例2

输入

{"train": [[1, 0], [2, 1], [3, 1], [4, 0]], "test": [[0.5], [2], [3.5]]}

输出

[0, 1, 1]

说明

训练集只有 1 个指标，样本数 n = 4。指标值排序为 1, 2, 3, 4，候选分界值为 1.5、2.5、3.5。

对于 1.5：左组 [0]，右组 [1, 1, 0]，右组 $H_R=1-(\frac{1}{3})^2-(\frac{2}{3})^2=\frac{4}{9}$，所以 $Q=\frac{3}{4}\cdot\frac{4}{9}=\frac{1}{3}$。

对于 2.5：左组 [0, 1]，右组 [1, 0]，两侧 $H$ 均为 0.5，$Q=0.5$。

对于 3.5：左组 [0, 1, 1]，右组 [0]，左组 $H_L=\frac{4}{9}$，所以 $Q=\frac{1}{3}$。

1.5 和 3.5 并列最优，按规则取更小的分界值 1.5。左组预测 0，右组预测 1。测试中 0.5 <= 1.5 输出 0；2 > 1.5、3.5 > 1.5 输出 1。

样例3

输入

{"train": [[5, 1], [5, 0]], "test": [[5], [5]]}

输出

[0, 0]

说明

训练集只有 1 个指标，两个样本的指标值均为 5，不存在相邻且不相等的指标值，因此没有可用候选分界值。

使用整个训练集的多数类别：标签 0 和 1 各出现 1 次，数量相同，默认预测 0。

两个测试样本均输出 0。

样例4

输入

{"train": [[1, 0], [1, 1], [2, 0], [2, 1]], "test": [[1], [2], [3]]}

输出

[0, 0, 0]

说明

训练集只有 1 个指标，排序后指标值为 1, 1, 2, 2。由于相同值之间不产生候选，唯一候选分界值为 1.5。

左组为前 2 个样本 [0, 1]，右组为后 2 个样本 [0, 1]。左组和右组的混杂度分别为 $H_L=1-(\frac{1}{2})^2-(\frac{1}{2})^2=0.5$、$H_R=0.5$，加权混杂度 $Q=\frac{2}{4}\cdot 0.5+\frac{2}{4}\cdot 0.5=0.5$。

由于左右组内 0 和 1 数量均相等，左右预测类别都取 0。因此无论测试样本落在哪一侧，输出均为 0。