ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1291. Шестерёнки

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!!!
Послано ANDRIY pmi [LNU] 22 июл 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!!!
Послано Tbilisi SU: Eldar Bogdanov 2 окт 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!!!
Послано ANDRIY [LNU] 5 окт 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.