白準Python[2018]秀之和5

白駿2018号:獣の和5

質問する

任意の自然数Nは、いくつかの連続する自然数の和として表すことができる.ある自然数(1<=N<=10000)について、このnをいくつかの連続した自然数の和の指数として表したいと思います.この場合、使用する自然数はN以下であるべきである.
例えば、15を表す方法は、15、7+8、4+5+6、1+2+3+4+5の4種類がある.逆に10を表す方法は10,1+2+3+4の2種類がある.
Nを入力し、出力指数のプログラムを作成してください.

入力

最初の行は整数Nを与える.

しゅつりょく

入力された自然数Nの出力は、いくつかの連続自然数の和を表す指数である.

入力例1

15

プリメモリ出力1

4

に答える

最初はシルバー5問だったので二重でも時間を超えないと思います

N = int(input())
result = 1

for i in range(N//2):
    cnt = i
    for j in range(i+1, N):
        cnt += j
        if cnt == N: result += 1
        elif cnt > N: break

print(result)

やっぱりタイムアウトだと思いました連続数字を加算するので、連続数字の和がNより大きい限り、開始数字の値を上げることができ、小さい場合は終了数字の値を上げることができます.

N = int(input())
result = 1

start_num = 1
end_num = 2
sum_nums = 3

while start_num <= N//2:
    if sum_nums < N:
        end_num += 1
        sum_nums += end_num
    elif sum_nums > N:
        sum_nums -= start_num
        start_num += 1
    else:
        result += 1
        end_num += 1
        sum_nums += end_num
        sum_nums -= start_num
        start_num += 1

print(result)