首页 > 试题广场 >

还原集合

[编程题]还原集合
  • 热度指数:1 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
小 Z 是一名黑客,他想获取小 Y 电脑上一个重要文件的内容。现在小 Z 已经知道这个重要文件由若干个整数组成,不妨称这些整数组成了一个可重集合 S,且小 Z 通过一些精妙的方法获取到了S每个子集的和(子集和就是子集中所有数的和),但他不知道如何还原出S。
不过,令小 Z 感到欣慰的是,他找到了你帮忙。

输入描述:
第一行有一个正整数 T,表示数据组数。
每组数据第一行有一个正整数 n,接下来 2 行,第一行 n 个整数 Si,第二行 n 个整数 Pi,每个数对 (Si, Pi) 表示和为 Si 的子集有 Pi 个。


输出描述:
对每组数据输出一行,先输出“Case #x: ”(x 为数据编号,从 1 开始),接着按升序输出 S 中的数。若有多种方案,则输出将 S 内所有元素从小到大排序后,字典序最小的一个,行末无空格。
数据保证至少存在一个合法的 S。
示例1

输入

3
8
0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
4
0 1 3 4
4 4 4 4
5
-2 -1 0 1 2
1 2 2 2 1

输出

Case #1: 1 2 4
Case #2: 0 0 1 3
Case #3: -2 1 1

备注:
1≤n≤10000, T≤50, |S|≤60, |Si|≤1010, Pi≥1, ∑Pi=2|S|

解释:

(1)|S|表示对应集合S中数的数量,而|Si|表示对应数值Si的绝对值。

(2)输出格式中的符号均为半角符号。

这道题你会答吗?花几分钟告诉大家答案吧!

问题信息

上传者:牛客301599号
难度:
0条回答 26浏览

热门推荐

通过挑战的用户

查看代码
还原集合