TASK: zerosum
LANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.000 secs, 3028 KB] Test 2: TEST OK [0.000 secs, 3028 KB] Test 3: TEST OK [0.000 secs, 3028 KB] Test 4: TEST OK [0.000 secs, 3028 KB] Test 5: TEST OK [0.000 secs, 3028 KB] Test 6: TEST OK [0.000 secs, 3028 KB] Test 7: TEST OK [0.000 secs, 3028 KB]All tests OK. 1 /* 2 PROG: zerosum 3 ID: jiafeim1 4 LANG: C++ 5 */ 6 7 #include < algorithm > 8 #include < iostream > 9 #include < fstream > 10 11 using namespace std; 12 13 char res[ 13 ] = { 0 }; 14 int top = 1 ; 15 long value = 0 ; 16 int n ; 17 std::ofstream fout( " zerosum.out " ); 18 void output() 19 { 20 for ( int i = 1 ;i <= n - 1 ; ++ i) 21 { 22 fout << i << res[i]; 23 } 24 fout << n << endl; 25 } 26 27 void work( long num, long last_num, char last_mark) 28 { 29 if (num == n) 30 { 31 if (res[num - 1 ] == ' ' ) 32 { 33 last_num = last_num * 10 + num; 34 } 35 else 36 { 37 last_num = num; 38 39 } 40 if (last_mark == ' + ' && value + last_num == 0 ) 41 output(); 42 if (last_mark == ' - ' && value - last_num == 0 ) 43 output(); 44 } 45 else 46 { 47 if (res[num - 1 ] == ' ' ) 48 last_num = last_num * 10 + num; 49 50 51 res[top ++ ] = ' ' ; 52 if (res[num - 1 ] == ' ' ) 53 work(num + 1 ,last_num,last_mark); 54 else 55 work(num + 1 ,num,last_mark); 56 -- top; 57 int temp_value = value; 58 if (res[num - 1 ] == ' ' || last_mark == ' ' ) 59 { 60 if (last_mark == ' + ' ) 61 value += last_num; 62 if (last_mark == ' - ' ) 63 value -= last_num; 64 if (last_mark == ' ' ) 65 value = last_num; 66 } 67 else 68 { 69 if (last_mark == ' + ' ) 70 value += num; 71 if (last_mark == ' - ' ) 72 value -= num; 73 last_num = num; 74 } 75 res[top ++ ] = ' + ' ; 76 work(num + 1 ,last_num, ' + ' ); 77 -- top; 78 res[top ++ ] = ' - ' ; 79 work(num + 1 ,last_num, ' - ' ); 80 -- top; 81 value = temp_value; 82 } 83 } 84 int main() 85 { 86 std::ifstream fin( " zerosum.in " ); 87 res[ 0 ] = ' ' ; 88 89 fin >> n; 90 work( 1 , 0 , ' ' ); 91 92 fin.close(); 93 fout.close(); 94 95 }