UVa 12908 - The book thief

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址

給一個 s ，為全部頁數加總(1+2+…+n)但缺了某一頁。
要求出 缺的頁數 和 這本書總共有幾頁(n)。

Solution

n 為總頁數，列出式子就是： $0 \lt \frac{n(n+1)}{2} - s \le n$
(總頁數的和) - (給的 s) = 缺的頁數，而缺的頁數會大於零、小於等於 n。

接著利用其中一邊不等式，同乘以 2
$$
n^2+n-2s\le2n\\
n^2-n-2s\le0\\
n(n-1)-2s\le0\\
$$

有兩段解，但另一個是負的，只考慮正的，將 $n = \sqrt{2s}$，看有沒有滿足。
因為是 $n(n-1)$ 要記得將結果向上取整($\lceil\sqrt{2s}\rceil$)，以免取得過小無法滿足另一邊的不等式。
沒有滿足的話就減一即為答案(n)。

用另一邊也行，但要換成向下取整($\lfloor\sqrt{2s}\rfloor$)，且不滿足的話是將 n 加一。
$$
\frac{n(n+1)}{2} - s > 0\\
n(n+1) - 2s > 0\\
$$

e.g. s = 6

$$
n^2 - n - 12 \le 0\\
n^2 + n - 12 \gt 0\\
$$

畫起來就像(不考慮負的)：
*: including
o: excluding

--------*
    o--------
    3   4

n = 4, lost = 4
(1 + 2 + 3 + 4) - 4 = 6

Code

UVa 12908

#include <cstdio>
#include <cmath>

char str[11];
inline int read()
{
    fgets(str, 11, stdin);
    if (str[0] == '0')
        return 0;

    int n = 0;
    for (int i = 0; str[i] != '\n'; ++i)
        n = n * 10 + str[i] - '0';
    return n;
}
int main()
{
    int s;
    while ((s = read()) != 0)
    {
        int s2 = s << 1;
        /*
        //n^2 - n - 2s <= 0
        int n = ceil(sqrt((double)(s2)));        
        int nn = n * n;
        if (nn - n > (s << 1))
        {
            nn -= (n << 1) - 1; //(n)^2 - (n*2-1) = (n-1)^2
            --n;
        }
        printf("%d %d\n", ((nn + n) >> 1) - s, n);
        */

        //n^2 + n - 2s > 0
        int n = floor(sqrt((double)(s2)));
        int nn1 = n * (n + 1);
        if (nn1 <= s2)
        {
            nn1 += (++n) << 1; //(n*(n+1)) + (n+1)*2 = (n+1)*(n+2)
            //++n;
        }
        printf("%d %d\n", (nn1 >> 1) - s, n);
    }

    return 0;
}