bieuthuczero
quoc14
plain_text
a month ago
1.5 kB
1
Indexable
Never
caidat
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; }
Leave a Comment