NYOJ 215 Sum

忘是亡心i 2022-09-19 10:39 48阅读 0赞

## Sum ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

Consider the natural numbers from 1 to N. By associating to each number a sign (+ or -) and calculating the value of this expression we obtain a sum S. The problem is to determine for a given sum S the minimum number N for which we can obtain S by associating signs for all numbers between 1 to N.  
  
For a given S, find out the minimum value N in order to obtain S according to the conditions of the problem.

输入

The input consists N test cases.  
The only line of every test cases contains a positive integer S (0< S <= 100000) which represents the sum to be obtained.  
A zero terminate the input.  
The number of test cases is less than 100000.

输出

The output will contain the minimum number N for which the sum S can be obtained.

样例输入

3
    12
    0

样例输出

2
    7

思路：1 to N包含+-号时，其最大值和最小值是 N\*(N+1)/2 和 -N\*(N+1)/2  
因此 1 -1~1 所有奇数 n n  
2 -3~3 所有奇数 n+1 n+1  
3 -6~6 所有偶数 2n 2n  
4 -10~10 所有偶数 2n+2 2\*(n+1)  
5 -15~15 所有奇数 3n 3n n \* (n+1)/2  
6 -21~21 所有奇数 3n+3 3\*(n+1) n / 2 \* (n+1)  
另S = N\*(N+1)/2 -> 2\*S = N\*(N+1)  
2\*S/N 与N的奇偶性质不同,且N的值小于sqrt(2\*S);

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

发表评论取消回复

表情：

评论列表（有 0 条评论，48人围观）

还没有评论，来说两句吧...

相关阅读

相关 NYOJ 215 Sum

Sum 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 Consider the natural numbers from 1 to

忘是亡心i/ 2022年09月19日 10:39/ 0 赞/ 49 阅读

相关 215.emoji 表单验证

效果 (源码网盘地址在最后) ![f6779e44f0cdcb2bbb2c59073e86441c.gif][] 源码 index.html <!DOC

Myth丶恋晨/ 2022年09月07日 06:11/ 0 赞/ 65 阅读

相关 NYOJ 122 Triangular Sums

Triangular Sums 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 The nth Triangular number,

迈不过友情╰/ 2022年08月25日 02:09/ 0 赞/ 20 阅读

相关 NYOJ 308

Substring 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述 You are given a string input.

客官°小女子只卖身不卖艺/ 2022年06月17日 13:20/ 0 赞/ 168 阅读

相关 NYOJ 248

BUYING FEED 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述 Farmer John needs to travel

清疚/ 2022年06月17日 10:28/ 0 赞/ 161 阅读

相关 NYOJ 168

房间安排时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会。于

冷不防/ 2022年06月17日 05:53/ 0 赞/ 167 阅读

相关 NYOJ 541

最强DE 战斗力时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述春秋战国时期，赵国地大物博，资源非常丰富，人民安居乐业。但许多

Myth丶恋晨/ 2022年06月16日 03:48/ 0 赞/ 197 阅读

相关 sum(sum()) 含义

sum(sum(y)) 求矩阵y所有元素的和。 sum(y) 是对矩阵各个列求和例如： y=\[1 2 ; 3 4 \] ====》 y = 1 2

柔光的暖阳◎/ 2022年05月18日 08:18/ 0 赞/ 217 阅读

相关 UVA 215 电子表格计算器

> 电子表格计算器 UVA - 215 > > A spreadsheet is a rectangular array of cells. Cells contain da

左手的ㄟ右手/ 2022年05月15日 23:18/ 0 赞/ 133 阅读

相关 leetCode215

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: [3,2,1,5,

秒速五厘米/ 2022年01月23日 05:09/ 0 赞/ 153 阅读