Rikka with Subset

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1442 Accepted Submission(s): 723

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has n positive A1−An and their sum is m. Then for each subset S of A, Yuta calculates the sum of S.

Now, Yuta has got 2n numbers between [0,m]. For each i∈[0,m], he counts the number of is he got as Bi.

Yuta shows Rikka the array Bi and he wants Rikka to restore A1−An.

It is too difficult for Rikka. Can you help her?

Input

The first line contains a number t(1≤t≤70), the number of the testcases.

For each testcase, the first line contains two numbers n,m(1≤n≤50,1≤m≤104).

The second line contains m+1 numbers B0−Bm(0≤Bi≤2n).

Output

For each testcase, print a single line with n numbers A1−An.

It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.

Sample Input

2 3

1 1 1 1

3 3

1 3 3 1

Sample Output

1 2

1 1 1

Hint

In the first sample, $A$ is $[1,2]$. $A$ has four subsets $[],[1],[2],[1,2]$ and the sums of each subset are $0,1,2,3$. So $B=[1,1,1,1]$

//题意：给出 n，m 代表有 n 个数，和为 m ，设为数列 a[i]，将 a[i] 的所有子集，的和求出，记录种数，得到 b[i] ，现给出 b ，求 a

//还是太水了，这种题竟然没有一点思路，01背包的反向做法即可推出 a ，具体做法是先找到最小的不为0的 b[i] ，i 即为 a 中最小的，然后，b[j]-=b[j-i] , O(n*m)

 # include <cstdio>

 # include <cstring>

 # include <cstdlib>

 # include <iostream>

 # include <vector>

 # include <queue>

 # include <stack>

 # include <map>

 # include <bitset>

 # include <set>

 # include <cmath>

 # include <algorithm>

 using namespace std;

 #define lowbit(x) ((x)&(-x))

 #define pi acos(-1.0)

 #define eps 1e-8

 #define MOD 1000000007

 #define INF 0x3f3f3f3f

 #define LL long long

 inline int scan() {

     int x=,f=; char ch=getchar();

     while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 inline void Out(int a) {

     if(a<) {putchar('-'); a=-a;}

     if(a>=) Out(a/);

     putchar(a%+'');

 }

 #define MX 100005

 //Code begin...

 int dp[MX];

 int main()

 {

     int t = scan();

     while (t--)

     {

         int n = scan(),m = scan();

         dp[]=;

         for (int i=;i<m+;i++)

             dp[i] = scan();

         vector<int> ans;

         for (int i=;i<=n;i++)

         {

             int k;

             for (int j=;j<=m;j++)

             if (dp[j]!=)

             {

                 k = j;

                 ans.push_back(k);

                 break;

             }

             for (int j=k;j<=m;j++)

                 dp[j] -= dp[j-k];

         }

         for (int i=;i<n;i++)

             printf("%d%c",ans[i],i!=n-?' ':'\n');

     }

     return ;

 }

巴特西

Rikka with Subset

最新文章

热门文章