3. Латинские буквы T, U, Y, W закодированы двоичными числами: T
U
Y
W
111
011
100
110
Какая последовательность букв закодирована двоичной строкой 110011111110100?​

1) Из А только два пути - AB=7, AZ=57.

AZ слишком большой, для начала отбросим его.

Идём по AB=7.

 

2) Из B три пути: BC=5, BD=7, BE=27.

BE слишком большой, пока отбросим его.

2.1) Рассмотрим для BC=5 :

Из C есть только один путь, CD=3.

Рассмотрим для CD :

Из D есть DB, но нам незачем возвращаться; значит остаётся DE=2.

Рассмотрим для DE :

Из Е есть EB, но это возврат, есть EF=2 и EZ=8

2.1.1) Если мы идём по EF, то от F есть FZ=3

В итоге, получается: A-B-C-D-E-F-Z = 7+5+3+2+2+3 = 22

2.1.2) Если в предпоследнем шаге пойти по EZ=8, то получается A-B-C-D-E-Z = 7+5+3+2+8 = 25

 

2.2) Рассмотрим для BD=7

Этим шагом мы как бы перескочим B-C-D

Из D есть DC и DE, идти в С нет смысла, так что идём в DE=2

Из Е есть EF=2 и EZ=8

2.2.1) Для начала пойдём в EF=2, FZ=3

Получается A-B-D-E-F-Z = 7+7+2+2+3 = 21

 

2.2.2) Другой вариант, EZ=8

Получается A-B-D-E-Z = 7+7+2+8 =24

 

ответ уже найдет, выделен жирным, но в других задачах иногда нужно просмотреть абсолютно все пути.

1) Допустим, бумагу мы сложим в бак 3. Это будет 83 + 58 = 141.
Тогда в бак 2 надо сложить стекло или жесть.

1) а) Допустим, мы в бак 2 сложили стекло. Это будет 52 + 85 = 137.
Тогда в бак 1 кладем жесть. Это будет 95 + 75 = 170.
Всего 141 + 137 + 170 = 448 перемещений.

1) б) Допустим, мы в бак 2 сложили жесть. Это будет 64 + 75 = 139.
Тогда в бак 1 кладем стекло. Это будет 98 + 85 = 183.
Всего 141 + 139 + 183 = 463 > 448.

2) Допустим, бумагу мы сложили в бак 2. Это опять 83 + 58 = 141.
2) а) Кладем в бак 3 стекло. Это будет 98 + 52 = 150.
Тогда в бак 1 кладем жесть. Это будет 95 + 75 = 170.
Всего 141 + 150 + 170 = 461 > 448.

2) б) Кладем стекло в бак 1. Это будет 98 + 85 = 183.
Тогда в бак 3 кладем жесть. 64 + 95 = 159
Всего 141 + 183 + 159 = 483 > 448.

3) Положим бумагу в бак 1. Это будет 83 + 83 = 166.
3) а) Положим стекло в бак 2. Это будет 52 + 85 = 137.
Тогда жесть пойдет в бак 3. 64 + 95 = 159.
Всего 166 + 137 + 159 = 465 > 448.

3) б) Положим стекло в бак 3. Это будет 52 + 98 = 150.
Тогда жесть пойдет в бак 2. Это будет 64 + 75 = 139.
Всего 166 + 150 + 139 = 455 > 448.

Я рассмотрел все 6 вариантов разложить 3 мусора по 3 бакам.
ответ: минимальное количество перемещений равно 448.