Question

В химической лаборатории работают профессор и его помощник робот. Профессор готовится к сложному эксперименту, для которого ему нужно 10 колб с особой жидкостью. Профессор разлил всю имеющуюся у него жидкость по десяти колбам, так что в них оказалось (в миллилитрах): 16, 17, 17, 26, 20, 24, 23, 21, 16, 20 . Теперь он просит робота помочь ему уровнять объемы жидкости в колбах. За одну операцию робот может взять одну из колб и часть жидкости из нее (и даже всю жидкость) разлить по некоторым другим колбам (возможно, одной) в любом количестве. Робот умеет отмерять жидкость сколь угодно точно. За какое наименьшее количество операций ему удастся выполнить просьбу профессора?

Answer 1

мы решали такую задачу на олимпиаде, написали 5 переливаний.

Answer 2

Давайте посмотрим на объемы жидкости в колбах:

16, 17, 17, 26, 20, 24, 23, 21, 16, 20

Чтобы уровнять объемы в колбах, робот должен увеличить объемы колб с наименьшими значениями так, чтобы они стали равными объему колб с наибольшим значением. На данный момент, максимальный объем в колбах - 26 (два раза встречается), а минимальный - 16 (два раза встречается).

Шаг 1: Перенос из колбы с объемом 26 в две колбы с объемом 16. Результат: 16, 17, 17, 16, 20, 24, 23, 21, 16, 20

Теперь у нас есть две колбы с объемом 16 и две с объемом 17.

Шаг 2: Перенос из колбы с объемом 24 в три колбы с объемом 16. Результат: 16, 16, 16, 16, 20, 16, 23, 21, 16, 20

Теперь у нас есть пять колб с объемом 16.

Шаг 3: Перенос из колбы с объемом 23 в две колбы с объемом 16. Результат: 16, 16, 16, 16, 20, 16, 16, 21, 16, 20

Теперь у нас есть семь колб с объемом 16.

Шаг 4: Перенос из колбы с объемом 21 в две колбы с объемом 16. Результат: 16, 16, 16, 16, 20, 16, 16, 16, 16, 20

Теперь у нас есть девять колб с объемом 16.

Шаг 5: Перенос из колбы с объемом 20 в колбу с объемом 16. Результат: 16, 16, 16, 16, 16, 16, 16, 16, 20, 20

Теперь у нас есть две колбы с объемом 20 и восемь колб с объемом 16.

Шаг 6: Перенос из одной колбы с объемом 20 в две колбы с объемом 16. Результат: 16, 16, 16, 16, 16, 16, 16, 18, 18

Теперь у нас есть десять колб с объемом 16, и это наименьшее количество операций, которые роботу потребуется для уровнять объемы жидкости в колбах.

Ответ: Роботу потребуется 6 операций.