ZeroJudge B003: 運算式 + – 符號設定問題

給定一個運算式： ± 1 ± 2 ± 3 ± … ± n = k，你必須決定每個數字前的運算符號是 + 或 – 以找出最小的n值，使得此運算式等於k。

例如：若 k = 12，則運算式將會是：

– 1 + 2 + 3 + 4 + 5 + 6 – 7 = 12

而此時最小的 n 值是 7。

範例測資

範例輸入範例輸出
EOF 輸入，每一組測試資料一列，含有 1 個整數 k (0 <= |k| <= 1000000000)。對每一組測試資料輸出一列，輸出最小可能的 n (1 <= n) 使得運算式的結果為輸入的 k 值。
12
-3646397		7
2701

解題思路

從 1 到 n 將數字累加，當累加的數字超過 n 時，判斷累加的數字－n 是否是偶數，如果是偶數的話則目前跑到的數字即是答案。

如果 n 為負數的話就將其轉換成正數即可，並且累加的數字變數要開 Long Long Int。

範例程式碼－ZeroJudge B003: 運算式 + – 符號設定問題

#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
標籤

相關文章

發佈留言