Цитата:
Сообщение от Андрей Старцев
"если n - число сбрасываний, то сначала надо сбрасывать с этажа n,..."?
|
Потому что если он разобьётся, то у нас останется n-1 сбрасывание, за которые мы с одним оставшимся шаром легко найдём искомый этаж среди n-1 этажей снизу.
Потому что сбрасывание разделяет весь дом на две части - снизу та часть этажей, среди которых мы должны уметь находить искомый этаж пользуясь одним шаром, а сверху та часть, среди этажей которой мы должны уметь находить искомый этаж пользуюсь двумя шарами. В обоих случаях за n-1 сбрасывание.
Если мы для заданного числа сбрасываний хотим максимизировать этажность дома, то эти обе части желательно максимизировать. Поэтому если есть n сбрасываний, то лучше бросать с n-го этажа. Если разбился - точно найдём снизу за n-1 сбрасывание. Если не разбился - будем бросать дальше. Теперь можно бросать с этажа с номером n+(n-1). Потому что если разобьётся, то за n-2 сбрасываний мы его легко найдём среди этажей с номерами n+1, n+2, ..., n+(n-2). А если не разобьётся - продолжим дальше.
Соответственно, для 100-этажного дома рабочий алгоритм следующий.
1. Бросаем с этажа 14. Если разбился то второй шар бросаем пока не разобьётся подряд с 1-го, 2-го, ...13-го. Максимум 14 сбрасываний.
2. Если не разбился, то бросаем с 14+13 = 27. Если разбился, то второй шар бросаем пока не разобьётся подряд с 15-го, 16-го, ...26-го. Максимум 14 сбрасываний.
3. Если не разбился, то бросаем с 14+13+12 = 39. Если разбился, то второй шар бросаем пока не разобьётся подряд с 28-го, 29-го, ...38-го. Максимум 14 сбрасываний.
4. Если не разбился, то бросаем с 14+13+12+11 = 50. Если разбился, то второй шар бросаем пока не разобьётся подряд с 40-го, ...49-го. Максимум 14 сбрасываний.
5. Если не разбился, то бросаем с 14+13+12+11+10 = 60. Если разбился, то ... аналогично. Максимум 14 сбрасываний.
6. Если не разбился, то бросаем с 14+13+12+11+10+9 = 69. Если разбился, то ... аналогично. Максимум 14 сбрасываний.
7. Если не разбился, то бросаем с 14+13+12+11+10+9+8 = 77. Если разбился, то ... аналогично. Максимум 14 сбрасываний.
8. Если не разбился, то бросаем с 14+13+12+11+10+9+8+7 = 84. Если разбился, то ... аналогично. Максимум 14 сбрасываний.
9. Если не разбился, то бросаем с 14+13+12+11+10+9+8+7+6 = 90. Если разбился, то ... аналогично. Максимум 14 сбрасываний.
10. Если не разбился, то бросаем с 14+13+12+11+10+9+8+7+6+5 = 95. Если разбился, то ... аналогично. Максимум 14 сбрасываний.
11. Если не разбился, то бросаем с 14+13+12+11+10+9+8+7+6+5+4 = 99. Если разбился, то второй шар бросаем пока не разобьётся подряд с 96-го, 97-го, 98-го. Максимум 14 сбрасываний.
12. Если не разбился, то бросаем с 100-го. Конец. Максимум 12 сбрасываний.
В последнем случае всего 12 сбрасываний - это значит что 14 сбрасываний нам позволит найти искомый этаж не только в 100-этажном доме, но и в 99+3+2+1 = 105-этажном доме.
Какие чудеса! 105 - это 14*15/2 )))))
Надеюсь всё стало понятно, и почему нельзя гарантированно найти искомый этаж за 13 сбрасываний сможете легко доказать сами.
Кстати, у вашего автора вряд ли мировоззрение МЭПВ, так как решение его абсолютно правильное, только очень громоздкое.