Almost equilateral triangles
This problem is a little bit challenging. I take a look at my old code, it runs very fast. But I can not figure what I was doing since I did not write any comment. Then I spent an hour to analyze this problem and figured out why I wrote those magic code. It takes 4ms to get the answer.
Pythagorean triplet is critical for an efficient algorithm.
update 10/15/2017
The old code still not works very efficient especially when perimeter goes to 1e18. Actually, after the restriction equation on the sides is determined, it is easy to see that this problem is a Pell Equation problem. Pell equation has very rare solutions and it takes zero ms to figure out all triangles.
No comments:
Post a Comment