/prog/ - Solve using your language of choice

Name: Anonymous 2011-04-13 9:05

http://i56.tinypic.com/9qlh52.png

my solution in Java



import java.io.*;

import java.util.*;



public class ProblemF {

    

    public static void main(String[] args) throws Exception {

        BufferedReader fileIn = new BufferedReader(new FileReader("f.in"));

        

        String line = null;

        while ((line = fileIn.readLine()) != null) {

            int number = Integer.parseInt(line);

            if (number <= 0 || number >= 100000000) {

                break;

            }

            System.out.println(number +" : "+ getOrderedPairs(number));

        }

    }

    

    public static String getOrderedPairs(int number) {

        StringBuffer buff = new StringBuffer();

        

        int pairCount = 0;

        for (int i = 1; i <= number; i++) {

            for (int j = i; j <= number; j++) {

                int sum = getSummation(i, j);

                if (sum == number) {

                    pairCount++;

                    buff.append(" ("+ i +","+ j +")");

                    break;

                } else if (sum > number) {

                    break;

                }

            }

        }

        

        buff.insert(0, pairCount +" :");

        

        return buff.toString();

    }

    

    public static int getSummation(int tempA, int tempB) {

        int a = tempA - 1;

        int b = tempB;

        int sumB = ((b * (b + 1)) / 2);

        int sumA = ((a * (a + 1)) / 2);

        return sumB - sumA;

    }

    

}

Name: >>5 2011-04-13 10:37

And some testing:



(defun test-it (n) 

  (every (lambda (x) (= x n)) (mapcar (lambda (list) (apply #'sum-to list)) (find-all-sums n))))



;; will print any number where the sum a to b is not equal to what it should be

(loop for i from 1 to 99999999 unless (test-it i) do (print i))

This revealed a bug when handling even numbers, hence the revised version:



(defun find-all-sums (x &aux (2x (* 2 x)))

  (sort 

   (remove-duplicates

    (iter (for i from 2x downto 1)

          (for (values div mod) = (truncate 2x i))

          (and (zerop mod) 

               (not (zerop (mod div 2)))

               (let* ((a (/ (1- (+ div i)) 2))

                      (b (- (max div i) a)))

                 (collect (list b a)))))

    :key #'first)

   #'< :key #'first))

Solve using your language of choice

1 Name: Anonymous 2011-04-13 9:05

8 Name: >>5 2011-04-13 10:37

Name: Anonymous 2011-04-13 9:05

Name: >>5 2011-04-13 10:37