Интернет-банкинг в крольчатнике

[molch64]

Раз уж пошла пьянка

Напишу свою задачку про интернет-банкинг.

В некоторых интернет-банках (пример - телебанк от ВТБ24) есть такая очень хорошая штука под названием "отложенные распоряжения" Означает это следующее - у меня на счету 100 рублей, а мне надо перевести куда-то 300 рублей. Для этого я могу написать распоряжение на перевод этих денег, и оно просто осядет в системе, пока у меня на данном счету те самые 300 рублей не появятся. Как только у меня деньги появляются (ну там, в банкомате положил, или откуда-то пришли), распоряжение достается из глубин и те самые 300 рублей переводятся куда я хочу. Очень такая штука помогает в жизни!

А теперь задача.

В пресловутом и-банкинге у меня есть 2 рублевых счета, на которых по 0 рублей. А вообще, будем считать, что на счетах может быть только натуральное количество рублей без копеек. Так же в недрах этого банкинга уже лежит некоторое количество отложенных распоряжений на перевод денег между счетами, в том числе среди них (для упрощения) лежит распоряжение на перевод 64х рублей с первого счета на второй.

Одновременно на оба счета я кладу по 128 рублей.

Далее управление переходит к программе, которая действует следующим образом:
1: проверяет все отложенные распоряжения и находит те, которые можно в данным момент выполнить.
2: если количество таких распоряжений ровно одно, оно его выполняет (т.е. фактически производит перевод с одного счета на другой) и возвращается к шагу 1.
3: иначе программа завершает свою работу*

Вопрос - какое максимальное количество распоряжений можно выполнить с помощью этой программы.

Отдельно хочу пояснить пункт 3:
Если в какой-то момент ни одно распоряжение нельзя выполнить, то понятно, что дальше программа работать не будет.
А фишка вся в том, что если в один момент можно выполнить сразу несколько распоряжений, то программа не сможет выбрать, какое из них выполнять, зациклится и так же вылетит!

[Dendr]

У меня 6 получилось пока. Но кажется, должно быть 7. Если не 8 вообще...

[Alder]

Позвольте уточнить..
1.

Раз уж пошла пьянка
Так же в недрах этого банкинга уже лежит некоторое количество отложенных распоряжений на перевод денег между счетами

Здесь имеется в виду, что для каждого из двух счетов имеется несколько распоряжений на перевод денег с этого счета?

2.

Отдельно хочу пояснить пункт 3:
А фишка вся в том, что если в один момент можно выполнить сразу несколько распоряжений, то программа не сможет выбрать, какое из них выполнять, зациклится и так же вылетит!

правильно ли я поняла, что пока на счету Х денег, а также есть 2 распоряжения о переводе с него У1 и У2 денег, при чем У1< Х и У2 < Х, - никакое распоряжение выпоняться не будет?

[molch64]

2Alder:
1. Да, все распоряжения имеют вид перевода натурального числа рублей с первого счета на второй, или со второго на первый (направление задано)
2. Именно! В этом-то и суть задачи - в каждый момент рабочим распоряжением должно быть только одно:)

2Dendr
Пока что, разумеется, мало:)

[Dendr]

Во... довел до 9. Дальше уже тяжко. И пока все наобум больше. Логики не высматривается.

[Юляша]

Чегой-то много получается...
Не могу рассчитать закономерность, хотя ясно, что она есть... Ну и оптимальность не понятна...

Идем от конца к началу: в таблице - деньги на первом счету, на втором счету (в скобках - последний перевод)

1. 256 0 (<256) - распоряжений больше не осталось...
2. 0 256 (>256)
3. 256 0 (<255)
4. 1 255 (>254)
5. 255 1 (<253)
6. 2 254 (>251)
7. 253 3 (<249)
8. 4 252 (>246)
9. 250 6 (<242)
10. 8 248 (>237)
11. 245 11 (???)
12.???

И склейка с первым распоряжением не очевидна...

[Dendr]

Мне ход мыслей нравится.

Соответственно, надо дойти до момента, когда можно сделать только перевод 64 рубля. Потому что, явно же, что он дожен быть первым.

Upd. (тут был текст, основанный на ошибке) Индукция дает 4 "хода" для случая 2+2, 6 "ходов" для 4+4.

Можно предположить, что ответ для 128+128 - 16 "ходов"

[Dendr]

Да... так и есть. Ну, почти так.

Я продолжу Юляшин список... вроде ведь совсем немного осталось? А то я уж думал - может, ошибка где - но нет. Сам повторил - все сошлось.

11. 245 11 (<230)
12. 15 241 (>221)
13. 236 20 (<209)
14. 27 229 (>193)
15. 220 36 (<172)
16. 48 208 (>144)
17. 192 64 (<64)
б/н. 128 128

17 операций, все четко.

[molch64]

Однако быстро !

Да, действительно все четко:) Главное в решений этой задачи - не зацикливаться на доказательстве индукции на степенях двойки:) Мне это далось ой как не просто.

Нужная последовательность кстати строится нетривиальной формулой: a(k) = a(k-2)+a(k-3)+1, первые 3 - нули.

UPD:
А полное решение выглядит так:)

Пускай на k-м шаге перед переводом было a(k) денег на счету, на который деньги придут, и b(k), с которого деньги уйдут.
Т.е. фактически, a(k) - на меньшем, b(k) - на большем.
Направления переводов, очевидно, чередуются!
Запишем условие того, что распоряжение на k-м шаге нельзя выполнить двумя шагами ранее:)
Итак, на этом шаге мы перевели некую сумму с счета b(k), на нем стало лежать a(k+1) денег. Т.е. перевели мы b(k)-a(k+1). Эта сумма дожна быть хотя бы на один больше, чем та, которая лежала на этом же счету двумя шагами ранее, то есть b(k-2)
b(k-2)>=b(k)-a(k-1)-1
256-a(k-2)>=256-a(k)-a(k-1)-1
a(k-2)<=a(k)+a(k+1)+1
Вот собственно, и всё
Теперь перевернув нумерацию шагов (последний - первый), получим пресловутую последовательность a(t)<=a(t-2)+a(t-3)+1. Восстанавливая её с первыми двумя ноликами, получим 64 на нужном шаге и ответ 17

P.S> Когда я придумал и решал эту задачу, я даже не знал, что здесь будет такая последовательность, начинающаяся со степеней двойки (на четных местах), далее идущая по закоулкам, и чудом возвращающаяся на степень двойки в числе 64. А долго упорно пытался доказывать, что ответ 16, который бегает ровно по степеням двойки оптимальный.
Задачку хотел сюда послать чуть попозже, но раз уж пошла последовательность фибонначи, то что-бы не за компанию это тоже сюда подсунуть

[molch64]

Теперь про саму последовательность.

Называется она "... rabbits"*

Причем здесь кролики?
А притом, что сама-то последовательность Фибоначчи (обсуждавшаяся в соседнем треде) возникла из задачи, исторически сформулированной так:
В начальный (нулевой) период имеется пара кроликов (только родились).
Начиная со следющего периода (первого) эти кролики, пардон, совокупляются, таким образом начиная приносить по новой паре кроликов каждый период, начиная со второго.
Каждая пара кроликов в период рождения только растет, на следующий период уже совокупляется, а через период и далее приносит по паре нового потомства в период.
По индукции и доказывается, что x(k+2) = x(k+1) + x(k), x(1)=x(0)=1. Из этой задачи последовательность Фибоначчи и возникла.

А теперь задача:

Как нужно модифицировать предыдущую задачу, чтобы получить последовательность из задачи про отложенные распоряжения?
Ниоткуда извне кролики появляться не могут

P.S> Выпишу ещё раз первые несколько чисел нужной последовательности:
1, 1, 2, 3, 4, 6, 8, 11, 15, 20, 27, 36, 48, 64, 85, 113, 150
Нолики отбрасываем.

* слово под троеточием пока что скрыл

[Dendr]

Называется она "... rabbits"*
......
* слово под троеточием пока что скрыл

Так тоже мне тайна мадридского двора
Кролики только у одного были. На Д начинается, на Е заканчивается, но не Депардье.

[molch64]

Так тоже мне тайна мадридского двора
Кролики только у одного были. На Д начинается, на Е заканчивается, но не Депардье.

Ну дело в том, что "... rabbits" - это уже название модификации последовательности [не Депардье].
Так что сам этот клетчатый кроликосажатель [не Депардье], насколько я знаю, тут не причем
Это слово - некая особенность модификации, которая является подсказкой к задаче. Поэтому и скрыл.
Когда отгадается, в чем модификация, быстринько отгадается и слово. Благо, одну из его букв Dendr уже отгдал

[team55]

Называется она "... rabbits"*
......
* слово под троеточием пока что скрыл

Так тоже мне тайна мадридского двора
Кролики только у одного были. На Д начинается, на Е заканчивается, но не Депардье.

эти кролики, пардон, совокупляются,

Интересно, я один про совсем другое слово подумал?

[Судовой_Врач]

Fibonacci Rabbits
Именно благодаря Фибо кролики и плодятся