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;
}
(defun func (string &optional acc)
(if lst
(loop for x from 0 to (1- (length array))
for i in array do
(if (eq i ":")
(func (cdr lst) (cons (aref (1- x) array) acc))))
acc))
Kinda, that should PROBABLY do it, I haven't tested it though.
At first I wrote a naive solution like you, but noticed it was SLOW AS FUCK even when I cranked up the optimization settings:
(asdf:oos 'asdf:load-op '#:iterate)
(use-package '#:iterate)
(declaim (optimize (speed 3) (safety 0)))
(declaim (inline sum-to))
(defun sum-to (a b)
(declare (fixnum a b))
; (loop for i from a to b sum i) ; naive/slow
(the fixnum (/ (- (* b (1+ b)) (* a (1- a))) 2))
;(the fixnum (/ (* (1+ (- b a)) (+ b a)) 2))
)
;; too slow O(n*n), starts being unusable at ~10^6, when it takes longer than a minute per number
(defun find-all-sums (x)
(iter outer (for i from 1 to x)
(iter (for j from i to x)
(when (= (sum-to i j) x)
(in outer (collect (print (list i j))))))))
So I wrote this instead:
;; instead we use some math and make it O(n)
(defun find-all-sums (x)
(sort
(remove-duplicates
(iter (with 2x = (* 2 x))
(for i from x downto 1)
(for (values div mod) = (truncate 2x i))
(when (zerop mod)
(let* ((a (/ (1- (+ div i)) 2))
(b (- (max div i) a)))
(collect (list b a)))))
:key #'first)
#'< :key #'first))
Let's test it on the highest number:
CL-USER> (time (find-all-sums 99999999))
Evaluation took:
1.469 seconds of real time
1.468750 seconds of total run time (1.468750 user, 0.000000 system)
100.00% CPU
3,541,887,882 processor cycles
0 bytes consed
>>29
Oh, I see... I do like abusing my Lisp-2 like that.
Name:
Anonymous2011-04-13 20:23
open System
let orderedPairs x = List.rev [ for b = x downto 1 do
for a = b downto 1 do
if (List.sum [a..b]) = x then yield (a, b) ]
let numbers =
let rec getNumbers x =
if (0 < x) && (x < 100000000) then x :: getNumbers(int(Console.ReadLine()))
else []
getNumbers(int(Console.ReadLine()))
let rec orderedPairsString orderedPairsX =
match orderedPairsX with
| (a, b) :: t -> "(" + string(a) + ", " + string(b) + ") " + orderedPairsString(t)
| [] -> ""
What point in finding those pairs? They help to increase cow milking or make aircraft materials more reliable?
Name:
Anonymous2011-04-13 20:48
>>32
It's a toy problem for toy languages. That is why this thread is full of Haskell and ML.
Name:
Anonymous2011-04-13 21:15
in brainfuck ++++++++[->++++<]>>>++++++[<++++++>-]<++++[->+>
+>+<<<]>>++++>+>,.<<<<.>>>>>++++++++[-<------>]
<[->+>>>+>>>+<<<<<<<]+>+<[>[->+>+<<]>>>[->+>+<<
]>[-<+<+>>]<<+<[-<+>>>>>-<<<<]>[->>>[-<+>>>+<<]
<[->+<]<<]>>>[-]>[->-->+<<]+>[[-]<[-]>]<[[-]+++
+++++++++[-<<<++++<<<++++>>>>>>]<<<<<<<<<<.>>>>
+.-<<<.>>>>>>.<<<<<.<<<.>>>>>>>>>>>++++++++++++
[-<<<----<<<---->>>>>>][-]]>>[-<<+>>]<<<<<<<<->
+<[->[-]>+<<]>>[-<<+>>]<[[-]>>->+<[->[-]>+<<]>>
[-<<+>>]<[[-]<<<<<[-]>>>>>]<[-<<<+>>>>+<]>[-<+>
]<<<]<<] http://codepad.org/NdgW7mgP
well, it actually solves for only a single digit but algorithm is correct. It just requires a little extra work for inputting and printing multiple digit numbers
Name:
Anonymous2011-04-13 21:45
What I came up with:
tr :: Int -> Int
tr n = n * (n-1) `div` 2
untr :: Int -> Int
untr n' = let n = fromIntegral n' in ceiling $ sqrt (n*2)
f :: Int -> [(Int, Int)]
f n = [(a,b) | b <- [2..n], let b' = tr (b+1), let a' = (b'-n), let a = untr a', tr a == a']
main = do x <- readLn
print $ f x
main
Not as good as some of the solutions here, but it solves the biggest case in half the needed time.
let orderedPairs x =
[ for b = 1 to x do
let rec checkFrom(n) =
if n < 1 then []
elif sumAtoB(n, b) > x then []
elif sumAtoB(n, b) = x then (n, b) :: checkFrom(n - 1)
else checkFrom(n - 1)
yield checkFrom(b) ] |> List.concat
let numbers =
let rec getNumbers x =
if (0 < x) && (x < 100000000) then x :: getNumbers(int(Console.ReadLine()))
else []
getNumbers(int(Console.ReadLine()))
let rec orderedPairsString orderedPairsX =
match orderedPairsX with
| (a, b) :: t -> "(" + string(a) + ", " + string(b) + ") " + orderedPairsString(t)
| [] -> ""
>>28 's algorithm in HASKAL (about 3 times slower than C)
import Data.List (foldl')
import System.Environment (getArgs)
fst4 (t, _, _, _) = t
orderedPairs :: Int -> [(Int,Int)]
orderedPairs m =
fst4 $ foldl' (\ (xs, s, a, b) n ->
let b' = n
s' = s+b'
(s'', a') = reduce (s', a)
in if s''==m then ((a',b'):xs, s''-a', a'+1, b')
else (xs, s'', a', b')) ([], 0, 0, 0) [1..m]
where reduce (s, a) =
if s>m then reduce (s-a, a+1)
else (s, a)
main :: IO ()
main = do
args <- getArgs
let n = read (head args)
putStrLn $ show (orderedPairs n)
>>42
Fuck you, I am not bound by the rules of your stupid game.
i like to drnikj sperm from my spermbottle while waring my sperm necklace" - u
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
FUCK YOU I WON'T DO WHAT YOU TELL ME
fucking fag
Name:
Anonymous2011-04-15 0:36
>>42
There's no reason to be afraid of languages with high-order features. If you can't take lambdas I'm afraid you're a bit of a retard when it comes to being a programmer. (Don't get me wrong, C is great... but only when you need it.)
>>42
My code is pretty fast and portable, it's also better than OPs, so you can fuck off.
A language isn't a toy language, just because it's not popular in the ENTERPRISE.
And >>63 is the average imageboarder. The most peculiar characteristic of this subhuman species is the complete lack of any mental skill whatsoever.
As we can see, they refer as themselves as ``i'', and speak a strange language (most likely a subset/dialect of (US) English), composed of words like ``>mfw'', ``>implying'', ``noko'', whose meaning is still unknown.
They seem to be particularly unfriendly, calling everyone a ``faggot'' (or ``fag'', in their language), but in the context of their restricted minds, it may be an act of courtesy. This may justify the complete lack of sage in their posts.
They also seem to have a strange fetish for green-coloured text.