CF1515A.Phoenix and Gold

传统题 时间 2000 ms 内存 256 MiB 3 尝试 1 已通过 1 标签

Phoenix and Gold

题目描述

Phoenix 收集了 nn 块金子,他想把它们一起称重,以感受自己的富有。第 ii 块金子的重量为 wiw_i。所有金子的重量互不相同。他会将这 nn 块金子一块一块地放到秤上。

这个秤有一个奇怪的缺陷:如果秤上的总重量恰好为 xx,秤就会爆炸。他能否以某种顺序将所有 nn 块金子都放到秤上,并且在整个过程中秤不会爆炸?如果可以,请帮他找出一种可能的放置顺序。

形式化地说,请重新排列数组 ww,使得对于每个 ii1in1 \le i \le n),都有 j=1iwjx\sum\limits_{j = 1}^{i}w_j \ne x

输入格式

输入包含多组测试用例。第一行为一个整数 tt1t10001 \le t \le 1000),表示测试用例的数量。

每个测试用例的第一行包含两个整数 nnxx1n1001 \le n \le 1001x1041 \le x \le 10^4),分别表示 Phoenix 拥有的金子数量和需要避免的重量。

每个测试用例的第二行包含 nn 个用空格分隔的整数(1wi1001 \le w_i \le 100),表示每块金子的重量。保证所有重量两两不同。

输出格式

对于每个测试用例,如果 Phoenix 无法将所有 nn 块金子放上秤而不让秤爆炸,输出 NO。否则,输出 YES,并在下一行输出重新排列后的数组 ww。如果有多种方案,输出任意一种即可。

说明/提示

在第一个测试用例中,Phoenix 先把重量为 33 的金子放到秤上,然后是重量为 22 的,最后是重量为 11 的。此时秤上的总重量依次为 335566。秤不会爆炸,因为总重量从未等于 22

在第二个测试用例中,秤上的总重量依次为 8899111114141818,从未等于 33

在第三个测试用例中,Phoenix 必须把重量为 55 的金子放到秤上,秤总会爆炸。

由 ChatGPT 4.1 翻译

样例

3
3 2
3 2 1
5 3
1 2 3 4 8
1 5
5
YES
3 2 1
YES
8 1 2 3 4
NO

在线编程 IDE

建议全屏模式获得最佳体验