ZeroJudge 解題筆記：c024. 10079 - Pizza Cutting

作者：王一哲
日期：2026年1月30日


ZeroJudge 題目連結：c024. 10079 - Pizza Cutting

解題想法

這題困難之處在於數學證明。假設切 $n$ 刀的最大分割數量為 $m$ 塊，先列出前幾項的數量 1. $n = 0, m = 1$ 2. $n = 1, m = 1 + 1 = 2$ 3. $n = 2, m = 2 + 2 = 4$ 4. $n = 3, m = 3 + 4 = 7$ 5. $n = 4, m = 4 + 7 = 11$ 如果要使分割數量最多，最後一刀要與前面每一刀都交會。若 $dp[n]$ 代表切 $n$ 刀分割的最大數量，由以上的式子可以看出 $$ \begin{align*} dp[n] &= dp[0] + dp[n-1] + n\\ &= 1 + 1 + 2 + \dots + (n-1) + n\\ &= 1 + \frac{n(n+1)}{2} \\ &= \frac{n^2 + n + 2}{2} \end{align*} $$

Python 程式碼

使用時間約為 34 ms，記憶體約為 3.8 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n < 0: break
    print((n*n + n + 2) // 2)

C++ 程式碼

用 int 會溢位，要用 long long。使用時間約為 4 ms，記憶體約為 84 kB，通過測試。

#include <cstdio>
typedef long long LL;

int main() {
    LL n;
    while(scanf("%lld", &n) != EOF && n >= 0) {
        printf("%lld\n", (n*n + n + 2) / 2);
    }
    return 0;
}