QOJ.ac

QOJ

実行時間制限: 1.0 s メモリ制限: 256 MB 満点: 100

#10918. 寻找样本

統計

在机器学习中,感知机(perceptron)是一种用于二分类的监督学习算法。二分类器是一个函数,它能够决定一个由数字向量表示的输入是否属于某个特定类别。它是一种线性分类器,即一种基于线性预测函数(结合一组权重和特征向量)进行预测的分类算法。

展示感知机训练过程的示意图。来源:Wikipedia, CC BY-SA 4.0。

在现代意义上,感知机是一种学习二分类器的算法,称为阈值函数:一个将输入 $\mathbf{x}$(实值向量)映射到输出值 $f(\mathbf{x})$ 的函数:

$$f(\mathbf{x}) = sign(\mathbf{w} \cdot \mathbf{x} + b)$$

$$sign(x) = \begin{cases} -1 & x < 0 \\ 0 & x = 0 \\ 1 & x > 0 \end{cases}$$

其中 $\mathbf{w}$ 是实值权重向量,$\mathbf{w} \cdot \mathbf{x}$ 是点积 $\sum_{i=1}^m w_i x_i$,$m$ 是感知机的输入数量,$b$ 是偏置。偏置将决策边界从原点移开,且不依赖于任何输入值。

现在,你有两个感知机 $f_1$ 和 $f_2$。你想要找到一个样本 $\mathbf{x}$,使得这两个感知机的分类结果不同。形式上,这意味着 $f_1(\mathbf{x}) \cdot f_2(\mathbf{x}) < 0$。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$ ($1 \le T \le 10$),表示测试用例的数量。

对于每个测试用例,第一行包含一个整数 $N$ ($1 \le N \le 200$),表示感知机的输入数量。第二行包含 $N+1$ 个整数,其中第 $i$ 个 ($1 \le i \le N$) 整数表示第一个感知机的 $w_i$,最后一个整数表示偏置 $b$。第三行包含 $N+1$ 个整数,以相同格式描述第二个感知机。

保证感知机的参数 ($w_i$ 和 $b$) 均为 $[-100, 100]$ 范围内的整数。

输出格式

对于每个测试用例,如果至少存在一个满足要求的样本,则输出该样本。输出一行,包含 $N$ 个实数,其中第 $i$ 个 ($1 \le i \le N$) 数字表示样本的 $x_i$。如果不存在,则输出字符串 “No”(不含引号)。

请注意,你输出的每个数字必须在 $[-10000, 10000]$ 范围内。此外,小数位数不得超过 11 位,否则由于检查程序(checker)的精度限制,即使你的解是正确的也可能无法通过(通常情况下,应尽量减少输出的小数位数以避免精度问题。检查程序由 C++ 编写并使用 double 数据类型)。保证如果存在解,则一定存在满足上述条件的解。

样例

输入格式 1

2
2
1 -1 1
1 -1 -1
2
1 -1 0
2 -2 0

输出格式 1

0 0
No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.