c004 - 10812 - Beat the Spread!

🔗 前往 ZeroJudge 原題

題目描述

題目給定兩隊比賽結束時的分數總和 (s) 以及分數差的絕對值 (d)。要求計算出兩隊各自的分數，如果存在解則輸出兩隊分數（分數大的在前），否則輸出 "impossible"。

解題思路

設兩隊分數分別為 x 和 y，則有以下兩個方程式：

1. x + y = s
2. |x - y| = d

由於 x 和 y 必須是非負整數，且 x >= y (輸出要求分數大的在前)，因此可以將第二個方程式拆解為兩種情況：

• x - y = d
• y - x = d

對於第一種情況，聯立兩個方程式可以解得 x = (s + d) / 2 和 y = (s - d) / 2。 對於第二種情況，聯立兩個方程式可以解得 x = (s - d) / 2 和 y = (s + d) / 2。

在計算 x 和 y 的過程中，需要檢查以下條件：

1. s 和 d 的奇偶性：如果 s 和 d 的奇偶性不同，則 (s + d) / 2 和 (s - d) / 2 不會是整數，因此無解。
2. x 和 y 的非負性：如果計算出的 x 或 y 小於 0，則無解。
3. x >= y: 確保輸出分數大的在前。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,b;
	cin >> a;
	while(cin >> a >> b){
		if(b>a||(a+b)%2==1||(a-b)%2==1)
			cout << "impossible\n";
		else
			cout << (a+b)/2 << " " << (a-b)/2 << "\n";
	}
}