Page 1 of 1
11467 - Pythagorean Triangles
Posted: Mon Jul 14, 2008 5:06 am
by baodog
Hi,
I can only come up with O(n^4) algo for generating answers from 1...2000, but is too slow.
How is O(n^3) possible? Some hint is appreciated. Thanks!
Re: 11467 - Pythagorean Triangles
Posted: Mon Jul 14, 2008 7:24 am
by baodog
Ahh, I found O(n^2logn) or Or O(n^3logn) for all 2000 cases.
Just shoot rays from single point.
Re: 11467 - Pythagorean Triangles
Posted: Mon Jul 14, 2008 11:59 am
by Monsoon
can anyone verify my output, thx
Code: Select all
1
2
100
500
911
1000
1500
1999
2000
0
Code: Select all
4
44
360484740
302474108252
3667235277376
5400281116712
29018935378348
79411432484400
79574509024528
Re: 11467 - Pythagorean Triangles
Posted: Mon Jul 14, 2008 12:08 pm
by Victor Barinov
My AC program gives the same answer except two last.
My answer for two last is:
1999
95302811479600
2000
95500247758096