11467 - Pythagorean Triangles

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

11467 - Pythagorean Triangles

Post by baodog » Mon Jul 14, 2008 5:06 am

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!

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11467 - Pythagorean Triangles

Post by baodog » Mon Jul 14, 2008 7:24 am

Ahh, I found O(n^2logn) or Or O(n^3logn) for all 2000 cases.
Just shoot rays from single point.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Re: 11467 - Pythagorean Triangles

Post by Monsoon » Mon Jul 14, 2008 11:59 am

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

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

Re: 11467 - Pythagorean Triangles

Post by Victor Barinov » Mon Jul 14, 2008 12:08 pm

My AC program gives the same answer except two last.

My answer for two last is:

1999
95302811479600

2000
95500247758096

Post Reply

Return to “Volume 114 (11400-11499)”