|
|
When i used dfs, i was getting "Division by zero" on 10 test. Then' i switched to bfs and got AC. Can you explain me: WHY? Some graph problems having very low rating (caravans, Ivan's car) are quite hard to solve while some other problems (like Gear-wheels, Labyrinth) have rating two times higher and are incredibly easy. TEST: 5 10 2 0 11 2 3 0 12 3 4 0 13 4 5 0 14 4 0 1 2 RES: 2/1 -20/11 5/3 -20/13 10/7 TEST: 5 20 2 4 0 40 1 3 0 60 2 0 70 1 5 0 100 4 0 1 5 RES: 5/1 -5/2 5/3 -10/7 1/1 TEST: 4 10 2 3 0 20 1 0 40 1 4 0 100 3 0 1 6 RES: 6/1 -3/1 -3/2 3/5 TEST: 3 3 2 0 100 1 3 0 3 2 0 1 15 RES: 15/1 -9/20 15/1 TEST: 5 10 2 3 4 5 0 20 1 0 30 1 0 40 1 0 50 1 0 1 20 RES: 20/1 -10/1 -20/3 -5/1 -4/1 What means if gear-wheel have only one cog? Edited by author 26.09.2004 20:25 In this test have some gear not connect from other Try this test 2 1 0 1 0 1 6 answer 6/1 0/1 Edited by author 18.04.2005 12:50 Последняя строка входа содержит два числа: номер шестерни, соединенной с кинетическим генератором и скорость V (1 <= V <= 1000), с которой она вертится. Скорость может быть как положительной, тогда считается, что шестерня крутится против хода часовой стрелки, так и отрицательной, тогда считается, что шестерня крутится по ходу часовой стрелки. - Получается, что шестерня первая крутится всегда против часовой стрелки! Connection scheme in test 12 is asymmetric. There are wheels i and j, that j-th wheel is listed in the list of i-th, but i-th is NOT listed in the list of j-th. if I wrote ... else write('0/1'); ... instead of ... writeln('0/1'); ... IMHO it's a Presentation, not WA:) There is no 'presentation error' on Timus 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 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... 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.
Last string of input contains INTEGER VALUE ???? Help me please. Yes, at least my AC program read it as an integer :) Edited by author 12.02.2006 21:30 |
|
|