Algoogle

Algorithm for Programming Contest

AOJ 2197 Sum of Consecutive Integers

Category: AOJ Tag: inchworm-method

Sum of Consecutive Integers

問題概要


解法


入力Nと等しくなる2つ以上の連続した数はいくつあるか.
leftとrightを決めてその間の合計がNより小さければright++
そうでなければleft++
等しくなったらカウントしてright++
rightがNに届いたら終了

コード


(2197.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

#define rep(i, a, b) for(int i = a; i < b; i++)

using namespace std;

int n;

int main(){
    while(cin >> n, n){
        int cnt = 0, left = 1, right =  2;
        int sum = left + right;
        while(right < n){
            if(sum < n){
                right++;
                sum += right;
            }else if(sum > n){
                sum -= left;
                left++;
            }else{
                cnt++;
                right++;
                sum += right;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

Comments