c024 - 10079 - Pizza Cutting

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算用 N 刀最多可以將披薩切成多少塊。輸入為 N，輸出為最大塊數。當輸入為負數時，程式結束。

解題思路

觀察披薩切割的規律可以發現，切割的塊數與切割的刀數之間存在一個固定的數學關係。

• 0 刀：1 塊
• 1 刀：2 塊
• 2 刀：4 塊
• 3 刀：7 塊
• 4 刀：11 塊

塊數的增量分別為 1, 2, 3, 4...，因此可以推導出切割 N 刀最多可以切成的塊數的公式為：1 + (1 + 2 + 3 + ... + N) = 1 + N * (N + 1) / 2 = (N * N + N + 2) / 2。 程式直接使用這個公式計算結果並輸出。

複雜度分析

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

程式碼

#include <iostream>

using namespace std;

int main (){
	
	long long int n=0,m=0;
	while(cin >> n){
		if(n>=0){
		m=(n*n+n+2)/2;
		cout << m << endl;
	}
	}
}