Задача Gears
Дан набор красных зубчатых колес различных радиусов. Из них можно собирать конструкцию, насаживая на оси, лежащие в одной плоскости (на рис.1 изображено 2, на самом деле в ряду может быть N последовательно размещенных колес). Имеется также достаточное количество синих зубчатых колес произвольных радиусов, которые можно вставлять в конструкцию (рис.2). Какое минимальное количество синих колес нужно вставить в конструкцию, чтобы все красные колеса вращались в одну сторону с одинаковой частотой вращения? Радиусы синих колес - не обязательно целые числа. На одну ось можно крепить не больше 2-х синих колес (они будут вращаться при этом с одинаковой угловой скоростью). Красные колеса имеют каждое свою ось, а каждое синее колесо (либо пара синих колес на одной оси) может быть сцеплено ровно с двумя красными.
|
|
|
|
Рис. 1 |
Рис. 2. |
Технические условия. Программа Gears читает с клавиатуры количество красных колес N (2≤N≤10000) а далее - радиусы этих колес (N натуральных чисел, каждое из которых не больше 10000). Все числа записаны одной строкой через пробелы. Программа выводит на экран единственное число - искомую величину.
| Пример
Ввод 3 10 20 10 |
Вывод 3 |
На рисунке предложенная конструкция (вид сверху) |