HDOJ 2058 The sum problem

Problem Description
Given a sequence 1,2,3,……N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.

Input
Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.

Output
For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.

Sample Input
20 10
50 30
0 0

Sample Output
[1,4]
[10,10]

[4,8]
[6,9]
[9,11]
[30,30]

题目的意思:输入两个整数N,M。 N, M( 1 <= N, M <= 1000000000),如果在范围[1,M]内连续整数的和为N,按从小到大次序输出所有这样的连续段,当输入的M,N都为0时结束。
计算的思路:
不考虑子列的终点,而是考虑子列的起点和子列元素的个数,分别记为i,j。由等差数列求和公式,得(i+(i+j-1))*j/2==M ,即(2*i+j-1)*j/2==M(2式),故得i=(2*M/j-j+1)/2,将i,j代回2式,成立则[i,i+j-1]满足条件。注意j最小为1,而由2式,得(j+2*i)*j=2*M,而i>=1,故j*j<=(int)sqrt(2*M).

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            if(m==0&&n==0){
                return ;
            }

            int j =(int)Math.pow(2.0*m, 0.5);
            for(j=j;j>0;j--){
                int i;
                i = (2*m/j-j+1)/2;
                if(j*(j+2*i-1)/2==m){
                    System.out.println("["+i+","+(i+j-1)+"]");
                }
            }
            System.out.println();
        }
    }
}
时间: 2024-09-23 05:47:54

HDOJ 2058 The sum problem的相关文章

LeetCode之K sum problem

做过leetcode的人都知道, 里面有2sum, 3sum(closest), 4sum等问题, 这些也是面试里面经典的问题, 考察是否能够合理利用排序这个性质, 一步一步得到高效的算法. 经过总结, 本人觉得这些问题都可以使用一个通用的K sum求和问题加以概括消化, 这里我们先直接给出K Sum的问题描述和算法(递归解法), 然后将这个一般性的方法套用到具体的K, 比如leetcode中的2Sum, 3Sum, 4Sum问题. 同时我们也给出另一种哈希算法的讨论. leetcode求和问题

[ACMcoder] Sum Problem

Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + - + n. Input The input will consist of a series of integers n, one integer per line. Output For each ca

HDOJ 1002 A + B Problem II

Problem Description I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines fol

HDOJ 1003 Max Sum

Problem Description Given a sequence a[1],a[2],a[3]--a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. Input The first line of the input contains an

ACM杭电1001 Sum Problem 为什么会报错Compilation Error

问题描述 importjava.util.Scanner;publicclassSumProblem{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);while(sc.hasNext()){intsum=0;inti=sc.nextInt();for(intj=1;j<=i;j++){sum+=j;}System.out.println(sum);}}} 解决方案 解决方案二:运行没问题呀解决方案三:你是说在本

HDOJ 1048 The Hardest Problem Ever(加密解密类)

Problem Description Julius Caesar lived in a time of danger and intrigue. The hardest situation Caesar ever faced was keeping himself alive. In order for him to survive, he decided to create one of the first ciphers. This cipher was so incredibly sou

HDOJ/HDU 1022 Train Problem I(模拟栈)

Problem Description As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes

HDOJ 2101 A + B Problem Too

Problem Description This problem is also a A + B problem,but it has a little difference,you should determine does (a+b) could be divided with 86.For example ,if (A+B)=98,you should output no for result. Input Each line will contain two integers A and

HDOJ 2055 An easy problem

Problem Description we define f(A) = 1, f(a) = -1, f(B) = 2, f(b) = -2, - f(Z) = 26, f(z) = -26; Give you a letter x and a number y , you should output the result of y+f(x). Input On the first line, contains a number T.then T lines follow, each line