Bieu thuc zero

Level 4
Biểu thức Zero
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

#1 0
#2 1
#3 1
#4 1
#5 1
#6 6
#7 10
#8 11
Time: 0.02300 s.

8

2
3
4
5
6
7
8
9

#include <iostream>
#include <time.h>

using namespace std;

int oo = 2000000000;

int T, n, arr[10], choose[10];
int result;

// 0: add, 1 - sub, 2 - merger
int calcArr(){
	int ans = 0;
	int prev = arr[0];
	int prevC = 0;

	for(int i = 0; i < n - 1; i++){
		if(choose[i] == 0 || choose[i] == 1){
			ans = (prevC == 0 ? ans + prev : ans- prev);
			prev = arr[i+1];
			prevC = choose[i];
		} else if(choose[i] == 2){
			prev = prev * 10 + arr[i+1];
		}
	}
	ans = (prevC == 0 ? ans + prev : ans- prev);

	return ans;
}


void backtrack(int index){
	if(index == n-1){
		int total = calcArr();
		if(total == 0) result++;
		return;
	}
	for(int i = 0; i < 3; i++){
		choose[index] = i;
		backtrack(index+1);
	}
}


int main(){
	// read input
	freopen("input.txt", "r", stdin);

	//calc time
	clock_t tStart, tStop;
	tStart = clock();

	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// input and initial
		cin >> n;
		result = 0;
		for(int i = 0; i < n; i++) arr[i] = i + 1;

		// solve problem
		backtrack(0);

		// output
		cout << "#" << tc << " " << result << "\n";
	}


	//calc time
	tStop = clock();
	cout.setf(ios::fixed);
	cout.precision(5);
	cout << "Time: " << double(tStop - tStart) / CLOCKS_PER_SEC << " s." << endl;

	return 0;
}