ACM UVA 10025 (The ? 1 ? 2 ? ... ? n = k problem)

题目：

解题思路：

1. 当 k=0 时，n=3
2. 当 k!=0 时，找到一个最小的 n，使得 n*(n+1)/2 大于等于 |k|，并且 n*(n+1)/2 - |k| 为偶数。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char **argv)
{
    int case_num = 0;
    int k = 0;

    scanf("%d", &case_num);
    for (; case_num > 0; case_num--) {
        scanf("%d", &k);
        printf("%d\n", find(k));
        if (case_num > 1) {
            printf("\n");
        }
    }

    return 0;
}

int find(int k)
{
    int n = 0;
    int s = 0;

    if (0 == k) {
        return 3;
    }

    /* abs(k) */
    k = k < 0 ? 0-k : k;

    /*
     * n*(n+1)/2 = k
     */
    n = (int)(sqrt((2*k + 0.25)) - 0.5);

    /*
     * find the minimum n
     */
    s = sum(n);
    while (s < k || ((s-k) % 2) != 0) {
        n++;
        s = sum(n);
    }

    return n;
}

int sum(int n)
{
    return n*(n+1) / 2;
}