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