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.

输入数据 1

15

输出数据 1

4

Source

USACO 2003 March Orange

描述

农夫约翰牛群中的奶牛都被编了号，并且打上了从1到N（1 <= N <= 10,000,000）的连续整数的烙印。当奶牛来到谷仓挤奶时，它们总是按照从1到N的顺序依次到来。

农夫约翰在大学时主修数学，并且热爱数字，他经常寻找数字规律。他注意到，当他的牛群中恰好有15头奶牛时，恰好有四种方式可以使任意一组一头或多头连续奶牛身上的数字之和等于15（与奶牛的总数相同）。这四种方式分别是：15、7 + 8、4 + 5 + 6 以及 1 + 2 + 3 + 4 + 5。

当牛群中的奶牛数量为10时，他能通过对连续奶牛身上的数字求和得到10的方式数量就减少到了2种：即1 + 2 + 3 + 4 和 10。

编写一个程序，计算出农夫约翰能够通过对连续奶牛身上的数字求和得到N的方式数量。请不要使用预计算的方法来解决这个问题。

输入

第1行：一个整数N

输出

第1行：一个整数，表示连续奶牛编号之和等于N的方式数量。 输入数据 1

15

输出数据 1

4

来源 美国计算机奥林匹克竞赛（USACO）2003年3月 橙色组

算法标签：

双指针扫描

题意分析

本题的核心是给定一个整数 N，它代表农夫约翰牛群中奶牛的数量，每头奶牛的编号是从 1 到 N 的连续整数。需要找出所有由连续编号的奶牛编号之和等于 N 的组合方式，并统计这些组合方式的数量。例如，当 N = 15 时，有 15、7 + 8、4 + 5 + 6、1 + 2 + 3 + 4 + 5 这四种组合方式；当 N = 10 时，有 1 + 2 + 3 + 4 和 10 这两种组合方式。

解题思路

可以采用双指针法来解决这个问题。使用两个指针 left 和 right 分别表示连续编号序列的起始和结束位置，然后计算从 left 到 right 这些编号的和 sum。 若 sum 等于 N，则找到了一种符合要求的组合方式，计数加 1，同时将 right 指针右移一位，继续寻找其他组合。 若 sum 小于 N，说明当前的连续编号序列和不够，将 right 指针右移一位，增大和。 若 sum 大于 N，说明当前的连续编号序列和过大，将 left 指针右移一位，减小和。

标程

#include<iostream>
using namespace std; 
int count_ways(int N) {
int count = 0;
int left = 1;
int right = 1;
int current_sum = 1;
while (left <= right && right <= N) {
    if (current_sum == N) {
        count++;
        right++;
        if (right <= N) {
            current_sum += right;
        }
    } else if (current_sum < N) {
        right++;
        if (right <= N) {
            current_sum += right;
        }
    } else {
        current_sum -= left;
        left++;
    }
}
return count;
} int main() {

int N;
cin >> N;
cout << count_ways(N) << endl;
return 0;
}