问题 4367 --还原集合

4367: 还原集合

题目描述

  小Z是一名黑客,他想获取小Y电脑上一个重要文件的内容。现在小Z已经知道这个重要文件由若干个整数组成,不妨称这些整数组成了一个可重集合S,且小Z通过一些精妙的方法获取到了$S$每个子集的和(子集和就是子集中所有数的和),但他不知道如何还原出$S$。
不过,令小Z感到欣慰的是,他找到了你帮忙。

输入

第一行有一个正整数$T$,表示数据组数。
每组数据第一行有一个正整数$n$,接下来2行,第一行$n$个整数$S_i$,第二行$n$个整数$P_i$,每个数对$(S_i,P_i)$表示和为$S_i$的子集有$P_i$ 个。

输出

对每组数据输出一行,先输出“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
输出#1 复制
Case #1: 1 2 4
Case #2: 0 0 1 3
Case #3: -2 1 1

提示

对于$20\%$的数据,$1\le n\le 8,\ T\le 10,\ |S|\le 6$。
对于$60\%$的数据,$|S|\le 20$,且其中每个整数都是非负的。
对于$100\%$的数据,$1\le n\le 10000,\ T\le 50,\ |S|\le 60,\ |S_i|\le 10^{10},\ P_i\ge 1,\ \sum P_i=2^{|S|}$。

序号 标题 作者 发表时间 费用 订购数 操作