AtCoder Regular Contest 070: C - Go Home

,

http://arc070.contest.atcoder.jp/tasks/arc070_a

solution

$x \le \sum_{n \le t} n$な最小の$t$が答え。愚直にやっても$O(\sqrt{X})$。

時刻と移動可能な座標を表にすると以下のように。

t: x
0: 0
1: 0 1
2: 0 1 2 3
3: 0 1 2 3 4 5 6
4: 0 1 2 3 4 5 6 7 8 9 10
5: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

implementation

#include <stdio.h>
int main() {
    int x; scanf("%d", &x);
    int t = 0;
    while (t*(t+1)/2 < x) ++ t;
    printf("%d\n", t);
    return 0;
}