UVA 10025(数学)
数学 UVa
2023-09-11 14:21:03 时间
The ? 1 ? 2 ? ... ? n = k problem
The ? 1 ? 2 ? ... ? n = k problem |
The problem
Given the following formula, one can set operators '+' or '-' instead of each '?', in order to obtain a given k
? 1 ? 2 ? ... ? n = k
For example: to obtain k = 12 , the expression to be used will be:
- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12
with n = 7
The Input
The first line is the number of test cases, followed by a blank line.
Each test case of the input contains integer k (0<=|k|<=1000000000).
Each test case will be separated by a single line.
The Output
For each test case, your program should print the minimal possible n (1<=n) to obtain k with the above formula.
Print a blank line between the outputs for two consecutive test cases.
Sample Input
2 12 -3646397
Sample Output
7 2701
先求出第一s=1+2+3+...+n>=k的第一个n,假设s-k为偶数那么此时n,就是最小值,否则最小值为n+1或n+2(由于连续的两个数里一定有一个奇数,就能改变s-k的奇偶性了);由于
首先n个数的和要和k奇偶性同样,由于无论怎么改变符号n个数的奇偶性不会变,奇偶性同样那么n-k就一定是偶数,n-k是偶数那么变号的数就应该是(n-k)/2,由于s》=k,s-(s-k)=1+2+...-(n-k)/2+....n=k;所以此时求出来的n一定能够构造出k,且为最小的,代码例如以下
#include<stdio.h> #include<math.h> int main() { int i,k,n,m; scanf("%d",&n); while(n--) { scanf("%d",&k); if(m==0)printf("3\n"); else { k=k>0?k:-k; m=sqrt(2*k); for(i=m;i*(i+1)<2*k;i++); while(1) if((i*(i+1)/2-k)%2)i++;//实际上两次之内就能够改奇偶性了 else break; printf("%d\n",i); } if(n)printf("\n"); } return 0; }
相关文章
- 【原创】开源Math.NET基础数学类库使用(11)C#计算相关系数
- AI涉及到数学的一些面试题汇总
- LeetCode-942. 增减字符串匹配【贪心,双指针,数学】
- 数学建模番外篇8:画图配色
- 数学建模暑期集训8:熵权法
- 数学建模学习笔记(二十二)灰色预测(下下)GM(2,1)
- Algorithm:数学建模大赛(CUMCM/NPMCM)之全国大学生数模竞赛简介 & 相关书籍、文章推荐等详细攻略
- 到达终点数字-递归做法和数学规律法
- 深度学习的数学基础要求
- 【2022高教社杯数学建模】C题:古代玻璃制品的成分分析与鉴别方案及代码实现(已经更新完毕)
- 【2022 年“SPSSPRO 杯”数学中国数学建模网络挑战赛】A题 人员的紧急疏散-第二阶段23页论文
- 【清风数学建模笔记】第十三讲:SVD和图形处理