Sort 10 Discussions, By:
Please Login in order to post a comment
Solved this problem in F# using Euclid's formula to generate primitive Pythagorean triplets, for each increasing the triplet count of the appropriate lenghts (ie, multiples of the sum of the triplet values). With some simple DP, one then has all answers precalculated.
Note that this last part is useful in this particular problem, since the number of tests can be high (10^5).
Lazy solution to dumb test cases: precalculate all the counts up to N=5e6 then return the corresponding value for each test case. You really should put more effort (or at least some effort) into reasonable/decent/interesting requirements.
Please give any hints regarding timeouts@tc4-6! A local profiling run on my submission (java.lang, T=10000, N in 4990000..5000000, no input scanning) executes in 2.767 seconds...Tc0-3 pass either (~20 ms).
Scanner -> BufferedReader, List<Integer> -> int, aggergated generation (of the triplets) and evaluation (of results) did it by the end of the day: Congratz 2me, thx anyway 2you
Scanner -> BufferedReader
List<Integer> -> int
any one can send code for this answer
Was stuck with the mindset to calculate the primitive triplets of a given perimeter (loop based on the perimeter) one after another, and it was too slow.
Then I swiched to looping on odd and even m and its corresponding n, and even with occasional gcd() does not make it unacceptably slow. The rest is just implementation of precalculation and dynamic programming. Takes more than 2s in Python, though.
There is a typo in the challenge title.
For 50 the answer should be 0.
Because according to your answer that is 6 which is only possible when you add all the right triangles of length <50.
But according to your question the lenght of wire must be equal to the sum of all the sides of triangle
but if you are giving 50 as your input and giving 6 as an output which means that you are incresing your count values for 12,24,30,36,40,48 which gives you answer 6. while doing that you are contradiciting 1 condition that is sum of edges should be equal to the given length.
please reply me soon with your suggestion.
Read carefully the problem and what should be the output, you are getting it:
"Because according to your answer that is 6 which is only possible when you add all the right triangles of length <50"
Well,the question is clear, but the example about "120" is absurd.By following the question 120 has 22 possibilities of forming a integer sided triangle.
I can see in your profile that you are Indian, and I suppose that English is not your native language. Many times the problem statement is an extra challenge for us that do not speak English natively, and is something that we must learn to overcome. A single word can change the things a lot, and the answer of the problem.
Yup...I completely agree with you on that...and btw it's "for us who do not" not "for us 'that' do not"...:P..no offence...:)
50cm answer should be 0
Yes it should be 0
Answer is 6, read carefully the problem
Yeah, Answer is correct.
It must be 6 only. Just read the problem statement again and you will get it.
Admin, can you please take a look at my code and tell where I am going wrong ? I am getting WA for the last 3 test cases..
Here's my submission ID:
maybe you stopped your m too soon (in my case I solved stopping m a little later...)
Can you please be a bit clearer ?
the first step of my algorithm is to generate all the primitive triples and their multiples with perimeter less or equal 5*10^6 using Euclid's formula, and in first instance I assumed that m<=1200 was sufficient to generate al the triples (I've approximated n=m, so max perimeter was near 4*1200^2) but this way I was loosing some triangles generated by higher m...
Please help me, I got wrong answer for every test case, but I don't know what is wrong with my solution. Below is my algorithm to check whether there is any 1 solution or not:
max = L/4
sol = 
for a in xrange(1,max+1):
b = (L*L-2*L*a)/float(2*(L-a))
# b is integer solution
b = int(b)
# a and b satisfy pythagoras theorem
# if solution is already more than 1
# Solution exactly 1
count = 0
for L in xrange(12,N+1):
T = int(raw_input(""))
for i in xrange(0,T):
N = int(raw_input(""))
I manually check this function and as far as I know this return correct answer. Which case do you think this algorithm fail to calculate? I know this is slow, but I wil think about it after this gives corect result.
No more comments