Question

В кабинете химии есть три колбы объёмами 6 мл, 20 мл и 35 мл. Обозначим их буквами A, B, C соответственно. Также у вас есть неограниченный запас реактива. Используя эти колбы вам необходимо отмерить ровно 1 мл реактива. При этом весь реактив, который будет налит в колбы, придётся вылить (он будет загрязнён от контакта с колбами), поэтому вы хотите потратить как можно меньше реактива, чтобы отмерить ровно 1 мл. С колбами можно выполнять следующие действия: Наполнить какую-то колбу реактивом до края. Вылить весь реактив из какой-то колбы. Перелить реактив из одной колбы в другую, пока в первой колбе не кончится реактив или вторая колба не заполнится целиком. Составьте алгоритм переливаний, в результате исполнения которого в какой-то из колб окажется 1 мл реактива, а объём использованного реактива будет как можно меньше. Для записи алгоритма используются следующие команды: >X Наполнить колбу X (вместо X должен быть один из символов A, B, C). X> Вылить реактив из колбы X (вместо X должен быть один из символов A, B, C). X>Y Перелить реактив из X в Y (вместо X и Y должны быть два различных символа из A, B, C). Нельзя переливать реактив из одной колбы в ту же самую колбу. Команды записываются по одной в строке. Например, следующая последовательность команд >B B>C C> обозначает, что сначала наполняется колба B, потом реактив из колбы B переливается в колбу C, потом из колбы C выливается весь реактив. Чем меньше реактива будет использовано для реализации вашего алгоритма, тем больше баллов вы получите.

Answer 1

Ответ:

>C   (Наполняешь 35мл)

C>B    (в В становится 20, в С 15)

>A   (Наполняешь 6 мл)

A>C (В А становится 0, в С 21)

B> (Выливаешь все из В)

C>B (В В становится 20, в С 1)

В колбе С теперь 1 мл

Объяснение:

Answer 2

Для решения этой задачи нужно использовать жадный алгоритм, который будет минимизировать использование реактива. В данном случае, мы можем воспользоваться следующим алгоритмом:

1. Начнем с пустой колбы D (это вспомогательная колба).

2. Наполним колбу B полностью (переливаем из колбы B в колбу D):

   B B>D

3. Затем перелейте из колбы C в колбу B (пока не останется места в B или пока C не опустеет). Это позволит нам перелить 1 мл из C в B: C>B

4. Вылейте содержимое колбы D (пустой вспомогательной колбы) обратно в C, чтобы не создавать дополнительной затраты реактива: D>C

5. Теперь у нас есть 1 мл реактива в колбе B.

Итоговая последовательность команд:

B B > D C > B D > C

Таким образом, вы сможете отмерить ровно 1 мл реактива, используя как можно меньше реактива.