20111024

ACM 913 Joana and the Odd Numbers

1, 3, 5, 7, ... , n,
加總可求出該行最後一個數的值:
1 + 3 + 5 + ... + n,
=> (1 + n) * [(n + 1) / 2] / 2,
=> [(1 + n) / 2] ^ 2。(1)
此值即為等差數列第N項,求N值:
1 + 2 * (N - 1)。 (2)
N用(1)代入
題目求第k - 2, k - 1, k項相加的值,
此值為3 * k - 2 - 4,
k用(2)代入。

直接寫化簡後結果:
(3 / 2) * (n + 1) ^ 2 - 9,
即為答案。

2^63 - 1要用long long type。
除法最後運算,要不然會被吃掉。

/* ACM 913
 * mythnc
 * 2011/10/24 21:38:34   
 * run time: 0.008
 */
#include <stdio.h>

int main(void)
{
    long long n;

    while (scanf("%lld", &n) != EOF) {
        n++;
        printf("%lld\n", 3 * n * n / 2 - 9);
    }
    return 0;
}

沒有留言: