poj 2140 Herd Sums

Description

The cows in farmer John's herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N. 

Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7+8, 4+5+6, and 1+2+3+4+5. 

When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10. 

Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem. 

Input

* Line 1: A single integer: N 

Output

* Line 1: A single integer that is the number of ways consecutive cow brands can sum to N. 

Sample Input

15

Sample Output

4

Source

USACO 2003 March Orange

입력으로 어떤 값 y가 주어질 때,

공차가 1인 등차수열 (x, x+1, x+2 .... x+n)을 이용하여 y를 표현할 수 있는 방법의 경우의 수를 출력하는 문제입니다.

문제에서 예를 들어준듯이

15는

15, 7+8, 4+5+6, 1+2+3+4+5 로 나타낼 수 있습니다.

제 풀이법은 다음과 같습니다.

일단 1부터 n까지의 합은 n*(n+1) / 2 이므로

1부터 n까지의 합으로 입력된 y의 값을 나타낼 수 있는지 확인합니다.

그때 만든 등차수열의 시작과 끝을 m과 n으로 둡니다.

등차수열의 합이 y보다 작으면 n을 늘려 sum에 더하고,

등차수열의 합이 y보다 크면 m을 늘려 sum에서 빼는 형식으로

알고리즘을 구현하였습니다.

이것을 이용하면 sum이 문제에서 주어진 int 범위를 넘지 않을것이며

알고리즘 또한 2*n 알고리즘으로 매우 빠른 속도로 문제를 해결할 수 있을 것입니다.

#include<iostream>

#include<string>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

int a,n=0,m=0;

int count=0;

int sum;

cin>>a;

for(n=1;;n++){

if( n*(n+1)/2 > a)

break;

}

n--;

sum = n*(n+1)/2 - m;

while(n<a+1){

if(sum == a){

//cout<<m+1<<"~"<<n<<endl;

count++;

n++;

sum+=n;

}

else if(sum > a){

m++;

sum-=m;

}

else if(sum < a)

{

n++;

sum+=n;

}

}

cout<<count<<endl;

}