Описание задачи
Дана куча шестерёнок (зубья + производитель). Нужно подобрать пару шестерёнок от одного производителя, чтобы передаточное отношение было максимально близко к запрошенному.
Формат входных данных
> Gears:
+ зубья производитель
+ зубья производитель
...
> Query:
? целевое_A:целевое_B,мин_пар
Логика поиска
- Для каждой пары (g1, g2) от одного производителя считаем g1/g2
- Сравниваем с targetA/targetB
- Ищем точное совпадение
- Если точного нет — ближайшее меньшее и ближайшее большее
Формат выходных данных
Exact:
сокращённое_отношение
* Производитель: зубья1:зубья2
Smaller ratio:
сокращённое_отношение
* Производитель: зубья1:зубья2
Larger ratio:
сокращённое_отношение
* Производитель: зубья1:зубья2
Примеры
Шестерёнки
+ 10 FirstgearCo
+ 17 FirstgearCo
+ 45 FirstgearCo
+ 93 FirstgearCo
+ 40 FirstgearCo
+ 24 FirstgearCo
+ 20 FirstgearCo
Query: ? 5:3,1
Exact:
5:3
* FirstgearCo: 40:24
40/24 = 5/3 — точное совпадение!
Query: ? 98:16,1
Smaller ratio:
93:17
* FirstgearCo: 93:17
Larger ratio:
93:10
* FirstgearCo: 93:10
Целевое: 98/16 ≈ 6.125. 93/17 ≈ 5.47 (меньше). 93/10 = 9.3 (больше).
Ключевые моменты
- Группировать шестерёнки по производителю
- Сравнивать дроби без float: a/b vs c/d → a*d vs c*b
- НОД для сокращения отношения