Bieu thuc zero
quoc14
c_cpp
20 days ago
2.1 kB
2
Indexable
Never
Backtrack
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; }
Leave a Comment