HDU 1194 Beat the Spread!：簡單數學推導

問題描述

給定兩個非負整數 s（和）與 d（絕對差），求兩個非負整數 x、y（x ≥ y），使得：

x + y = s
|x - y| = d

若無解，輸出 "impossible"。多組測試數據。

數學推導

設 x ≥ y，則 x - y = d。聯立方程：

x + y = s
x - y = d
-----------
2x = s + d  →  x = (s + d) / 2
2y = s - d  →  y = (s - d) / 2

解存在的必要條件：

1. s ≥ d（否則 y 為負）
2. s + d 為偶數（否則 x 非整數）
3. s - d 為偶數（等價於上條）

綜上：s ≥ d 且 (s + d) % 2 == 0。

算法流程

1. 讀入測試組數 T。
2. 對每組讀入 s, d。
3. 若 s < d 或 (s + d) % 2 != 0，輸出 "impossible"。
4. 否則計算 x = (s + d) / 2，y = (s - d) / 2，輸出 x y。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long s, d;
        cin >> s >> d;
        if (s < d || ((s + d) & 1)) {
            cout << "impossible\n";
        } else {
            long long x = (s + d) / 2;
            long long y = (s - d) / 2;
            cout << x << ' ' << y << '\n';
        }
    }
    return 0;
}

複雜度分析

時間 O(T)，空間 O(1)。純數學題，無需複雜數據結構。

易錯點提醒

• 輸入範圍未明確給出上限，建議用 long long 防溢出。
• 題目要求「largest first」，即先輸出 x 再輸出 y。
• 「non-negative integers」包含 0，s = d = 0 時解為 0 0。