Given an expression: ± 1 ± 2 ± 3 ± … ± n = k, you must determine the operation symbol, either + or –, in front of each number to find the smallest value of n such that this expression equals k.
For example, if k=12, the expression would be:
– 1 + 2 + 3 + 4 + 5 + 6 – 7 = 12
In this case, the smallest value of n is 7.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input is EOF (End Of File). Each test case is on a single line and contains one integer k (where 0 ≤ ∣k∣ ≤ 1,000,000,000). | For each test case, output a single line with the smallest possible value of n (where 1 ≤ n) such that the result of the expression equals the input value k. |
| 12 -3646397 | 7 2701 |
Thought Process
Sum the numbers from 1 to n. When the cumulative sum exceeds n, check if the difference between the cumulative sum and n is even. If it is even, then the current value of n is the answer.
If n is negative, convert it to a positive number. Also, ensure that the variable used for summation is of type Long Long Int.
Sample Code－ZeroJudge B003: Expression + – Symbol Setting Issue
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N) {
N = abs(N);
long long int sum = 0;
for (int i = 1; i<=1000000000; i++) {
sum += i;
if (sum == N) {
cout << i << "\n";
break;
}
if (sum > N) {
if ((sum - N) % 2 == 0) {
cout << i << "\n";
break;
}
}
}
}
}
//ZeroJudge B003
//Dr. SeanXD