ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1291. Gear-wheels

I got TL#10 and I don't know what to do because on my computer it works only 0.352 sec on max test! PROGRAMMERS please help me!!!
Posted by ANDRIY pmi [LNU] 22 Jul 2006 20:41
My algorithm is:
At first I make some class (for example wheel) which is like rational numbers
(with numerator and denumerator) then I read input data in static arrays,
after that I (recursivly) do initialisation of array of wheels starting from wheel,
that is connected to the kinetic-generator, in the end I output all initialised wheels.

// My CODE: Sorry but I know only C++
//1291_TL10
//I had deleted my code :)


Edited by author 03.02.2007 23:52

Edited by author 03.02.2007 23:52
Re: I got TL#10 and I don't know what to do because on my computer it works only 0.352 sec on max test! PROGRAMMERS please help me!!!
Posted by Tbilisi SU: Eldar Bogdanov 2 Oct 2006 19:42
I'm not very familiar with C++, so I can't understand your code normally, but I can try to help you anyway.

I solved it using BFS, but I think if you recurse only on wheels you haven't visited yet, it shouldn't cost much more time. The second thing is how you compute the reduced fraction. I did it dividing the numerator and denominator by their GCD until it was 1 just as I reached the wheel. If you are doing exactly the same, then try solving this problem using BFS...
Re: I got TL#10 and I don't know what to do because on my computer it works only 0.352 sec on max test! PROGRAMMERS please help me!!!
Posted by ANDRIY [LNU] 5 Oct 2006 13:56
Thank you.
Now I got AC.
My problem was in computing reduced fraction.
So I got AC with time 0.001 and without BFS!!
One more thank you.