Binary Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 794    Accepted Submission(s): 465
Special Judge

Problem Description
The Old Frog King lives on the root of an infinite tree. According to the law, each node should connect to exactly two nodes on the next level, forming a full binary tree.

Since the king is professional in math, he sets a number to each node. Specifically, the root of the tree, where the King lives, is 1. Say froot=1.

And for each node u, labels as fu, the left child is fu×2 and right child is fu×2+1. The king looks at his tree kingdom, and feels satisfied.

Time flies, and the frog king gets sick. According to the old dark magic, there is a way for the king to live for another N years, only if he could collect exactly N soul gems.

Initially the king has zero soul gems, and he is now at the root. He will walk down, choosing left or right child to continue. Each time at node x, the number at the node is fx (remember froot=1), he can choose to increase his number of soul gem by fx, or decrease it by fx.

He will walk from the root, visit exactly K nodes (including the root), and do the increasement or decreasement as told. If at last the number is N, then he will succeed.

Noting as the soul gem is some kind of magic, the number of soul gems the king has could be negative.

Given N, K, help the King find a way to collect exactly N soul gems by visiting exactly K nodes.
 

Input
First line contains an integer T, which indicates the number of test cases.

Every test case contains two integers N and K, which indicates soul gems the frog king want to collect and number of nodes he can visit.

⋅ 1≤T≤100.

⋅ 1≤N≤109.

⋅ N≤2K≤260.
 

Output
For every test case, you should output " Case #x:" first, where x indicates the case number and counts from 1.

Then K lines follows, each line is formated as 'a b', where a is node label of the node the frog visited, and b is either '+' or '-' which means he increases / decreases his number by a.

It's guaranteed that there are at least one solution and if there are more than one solutions, you can output any of them.

 

Sample Input
2 5 3 10 4
 

Sample Output
Case #1: 1 + 3 - 7 + Case #2: 1 + 3 + 6 - 12 +
 

Source
2015ACM/ICPC亚洲区上海站-重现赛（感谢华东理工） 



思路：
题意就是给你一个完全二叉树，现在从根节点1走，每次只能往下走。现在，给你一个N和K，K表示给你这个完全二叉树的前K行，从第1行到第K行有很多路径，希望找到一条路径能表示N，路径上的节点可取正也可取负，要求最后的和为N。我的思路是对树进行搜索，如果从上往下搜的话，那么每个节点都会有左右两个选择，每个选择又会有加减两种选择，所以太麻烦了。但是如果从叶子结点往上搜的话，他们到达根节点的路径只有一条，并且每个节点除以2就是它的上一个节点，并且每次都只有加和减两种选择，所以简单了许多。这里还采取的一种思想就是贪心，因为是从大的开始往小的找，那么一开始遇到大的就放并用sum统计，如果sum值>n，就表示当前东西放多了那就要减去这个值，直到最后运算完根节点如果sum正好等于n则说明这条路可以选择。一路上用a数组储存数值大小，b数组储存正负。
我这个题调了好久，一直都跟答案的结果不一样。。所以一直调。。结果一个小时过去了还是不一样。。最终突然发现这是个special judge 的题。。答案不唯一。。

并且猛然发现一个很好玩的事情，完全二叉树节点的规律就是二进制运算的规律，满2进1，最左边永远是最高位为1的那个二进制数，以后做二进制的题说不定会用到。。

代码： 
#include<iostream> 
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long a[100],b[100];
int n,k;//第k层 

bool dfs(long long sum,long long now,int d)//now是现在指向的数 
{
    if (d==0)
    {
        if (now==0&&sum==n) return 1;
        else return 0;
    }
    if (sum<n)
	{
		a[d]=now;
		b[d]=1;
		dfs(sum+now,now/2,d-1);
	} 
    else
	{
		a[d]=now;
		b[d]=0;
		dfs(sum-now,now/2,d-1);
	} 
}

int main()
{
    int t;
    scanf("%d",&t);
    for (int cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&n,&k);
        for (long long i=pow(2,k-1);i<pow(2,k);i++)
        {
      	   if (dfs(0,i,k)!=0) 
		   break;
        }
        printf("Case #%d:\n",cas);
        for (int i=1;i<=k;i++)
        {
        	printf("%d ",a[i]);
        	if(b[i])printf("+\n");
        	else printf("-\n");
        }
    }
}