Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Gears

Задача  Gears

Дано набір червоних зубчатих коліс різних радіусів. Із них можна збирати конструкцію, насаджуючи на осі, що лежать в одній площині (на мал.1   зображено 2, насправді в ряду може бути  N послідовно розміщених коліс). Є також  достатня кількість синіх  зубчатих коліс довільних  радіусів, які можна вставляти в конструкцію. (мал.2). Яку мінімальну кількість синіх коліс потрібно вставити в конструкцію, щоб всі червоні колеса оберталися в одну сторону  з однаковою частотою обертання? Радіуси синіх коліс - не обов'язково цілі числа. На одну вісь можна кріпити не більше 2-х синіх коліс (вони будуть обертатися при цьому з однаковою кутовою швидкістю).  Червоні колеса мають кожне свою вісь, а кожне синє колесо (або пара синіх коліс на одній осі) може бути зчеплене рівно з двома червоними.  

Мал. 1

Мал.  2.

 Технічні умови. Програма Gears читає з клавіатури кількість червоних коліс N (2≤N≤10000) а далі - радіуси цих коліс  (N натуральних чисел, кожне з яких не більше 10000). Всі числа записано одним рядком через пропуски. Програма виводить на екран єдине число - шукану величину.

    Приклад

Введення  3 10 20 10 Виведення 3       

На малюнку - пропонована

конструкція   (вигляд зверху)

                                                                                           


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"