Question

В первом сундуке лежит 111 монет, во втором — 222 монеты, в третьем — 333 монеты, а в четвёртом — 444 монеты. Иван-дурак может взять из любого сундука 3 монеты и разложить по одной монете в оставшиеся сундуки. Эту операцию он может повторить неограниченное количество раз. В любой момент Иван может забрать все монеты из одного сундука. Какое наибольшее количество монет он может себе обеспечить?

Answer 1

Ответ:

1107

Пошаговое объяснение:

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

так как на одной итерации мы добавляем в три из четырех сундуков монеты, то только в одном сундуке мы можем добиться 0

значит, с учетом двух утверждений картина с наибольшим количеством монет могла выглядеть следующим образом: 0 1 1 1108

на предыдущем шаге должно было быть 3 0 0 1107 - но такого быть не могло, согласно утверждениям выше

следующий вариант, где монет меньше, чем 1108, это 1107

этого варианта достичь можно, пользуясь следующим алгоритмом:

четвертый сундук не трогаем, а с остальными повторяем следующую операцию:

• берем сундук с наибольшим количеством монет и проводим операцию столько раз, сколько нужно, чтобы в сундуке осталось меньше трех монет

выглядит это так:

111 222 333 444

222 333 0 555

333 0 111 666

0 111 222 777

74 185 0 851

135 2 61 912

0 47 106 957

35 82 1 992

62 1 28 1019

2 21 48 1039

18 37 0 1055

30 1 12 1067

0 11 22 1077

7 18 1 1084

13 0 7 1090

1 4 11 1094

4 7 2 1097

6 1 4 1099

0 3 6 1101

2 5 0 1103

3 2 1 1104

0 3 2 1105

1 0 3 1106

2 1 0 1107

и он возьмет себе 1107 монет

Answer 2

Для решения этой задачи мы можем воспользоваться жадным методом. Идея заключается в том, чтобы каждый раз брать 3 монеты из самого большого сундука и разложить по одной монете в остальных трех сундуках. Повторяем этот процесс до тех пор, пока в одном из сундуков не останется меньше 3 монет.

Исходно сундуки выглядят так:

1. 111 монет
2. 222 монеты
3. 333 монеты
4. 444 монеты

Иван-дурак берет 3 монеты из 4-го сундука и размещает по одной монете в остальных:

1. 114 монет
2. 225 монет
3. 336 монет
4. 441 монет

Иван-дурак продолжает брать по 3 монеты из 4-го сундука и распределять их, пока в одном из сундуков не останется меньше 3 монет.

1. 117 монет

2. 228 монет

3. 339 монет

4. 438 монет

5. 120 монет

6. 231 монета

7. 342 монеты

8. 435 монет

9. 123 монеты

10. 234 монеты

11. 345 монет

12. 432 монеты

Теперь, если Иван-дурак заберет все монеты из 4-го сундука, то он получит 432 монеты. Это наибольшее количество монет, которое он может себе обеспечить.