bieuthuczero

Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + và - sao cho kết quả thu được bằng 0. Hãy viết chương trình tìm tất cả các khả năng có thể.

[Input]

Dòng đầu tiên là T số testcase. T dòng tiếp theo là các số tự nhiên N <= 9.

 

[Output]

Mỗi test case in ra “# ” theo sau là số lượng kết quả tìm được mỗi test case. 



[Sample] 

[Input]

1

7

 

[Output]

#1 6

 

Giải thích

1-2-3-4-5+6+7=0

1-2+3+4-5+6-7=0

1-23-45+67=0

1-23+4+5+6+7=0

1+2-3-4+5+6-7=0

1+2-3+4-5-6+7=0


8
2
3
4
5
6
7
8
9

#include <iostream>

using namespace std;

int n;
int res;
int x[13];
void back(int index)
{
	if (index == n + 1)
	{
		int tmpsum = 0;
		int tmpvalue = 1;
		for (int i = 2; i<=n; i++)
			if (x[i] == 0)
			{
				if (tmpvalue < 0)
					tmpvalue = (tmpvalue * 10 - i);
				else tmpvalue = (tmpvalue * 10 + i);
			} else
			{
				tmpsum += tmpvalue;
				tmpvalue = x[i] * i;
			}
		tmpsum += tmpvalue;

		if (tmpsum == 0)
		{
			res++;
		}
		return;
	}
	for (int i = -1; i <= 1; i++)
	{
		x[index] = i;
		back(index + 1);
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		cin >> n;

		res = 0;
		back(2);
		cout << "#" << tc << " " << res << endl;
	}
	return 0;
}