Triangle numbers and how to find them
I'm working on this problem: http://codeforces.com/contest/192/problem/A
(I'll try and explain myself though)
Given an integer, n, I have to find whether it can be made from two triangle numbers. Triangle numbers are any number representable as k*(k + 1) / 2 where k is a positive integer.
My idea is to find a triangle number, a, and then find whether b, which is added to a to make n, is also a triangle number.
It is a triangle number if sqrt(2*b - 0.25) - 0.5 has no reminder ie. ans % 1 == 0.
I had a problem doing this though, I need to use a double or float for the number, but I cannot use modulus operator with a double or float.
I decided to try something else as this wasn't working, but my current method is too slow - the program has a limit of 2seconds.
Any suggestions?
EDIT: Solved the problem - didn't use the equation method above but simply a brute force method with a few optimization tweaks.
(I'll try and explain myself though)
Given an integer, n, I have to find whether it can be made from two triangle numbers. Triangle numbers are any number representable as k*(k + 1) / 2 where k is a positive integer.
My idea is to find a triangle number, a, and then find whether b, which is added to a to make n, is also a triangle number.
It is a triangle number if sqrt(2*b - 0.25) - 0.5 has no reminder ie. ans % 1 == 0.
I had a problem doing this though, I need to use a double or float for the number, but I cannot use modulus operator with a double or float.
I decided to try something else as this wasn't working, but my current method is too slow - the program has a limit of 2seconds.
Any suggestions?
EDIT: Solved the problem - didn't use the equation method above but simply a brute force method with a few optimization tweaks.
Last edited on
Topic archived. No new replies allowed.