d096 - 00913 - Joana and the Odd Numbers

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在一個由奇數組成的三角形數字序列中，第 N 列最後三個數字的和。三角形的每一列都包含連續的奇數，且第 n 列有 n 個奇數。

解題思路

觀察題目給出的例子，可以發現第 n 列的最後一個數字是 2 * n^2 - 1。因此，第 n 列的最後三個數字分別是 2 * n^2 - 3、2 * n^2 - 1 和 2 * n^2 + 1。將這三個數字加總，得到 6 * n^2 - 3。然而，程式碼中使用了不同的公式 a=2*((n+1)/2)*((n+1)/2)-1 和 sum=a*3-6，這實際上是簡化後的結果，並且考慮了 n 為奇數和偶數的情況。

程式碼首先計算第 n 列的最後一個奇數 a。然後，根據 n 的值，計算最後三個奇數的和 sum。如果 n 大於 1，則使用公式 sum = a * 3 - 6。如果 n 等於 1，則 sum 等於 1。

複雜度分析

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

程式碼

#include <iostream>

using namespace std;
// 2 * ( ( N+1 ) / 2 ) ^ 2 -1
int main(){
	long long int n=0,a=1,sum=0;
	while(cin >> n){
		a=2*((n+1)/2)*((n+1)/2)-1;
		if(n>1){
			sum=a*3-6;
		}
		else if(n==1){
			sum=1;
		}
		cout << sum << endl;
		a=1;
		sum=0; 
	}
}