пятница, 28 марта 2014 г.

100 этажей

Небоскрёб
Имеется два одинаковых стеклянных шарика, а также стоэтажное здание. На каждом этаже есть балкон, с которого шарик можно сбросить. Если один шарик разбивается, то можно использовать второй. Как определить с помощью минимального количества бросков самый низкий этаж, при падении с которого шарик точно разбивается? Минимальное количество бросков нужно определить и предложить алгоритм действий.


update
Первый - svarog_777.
Ответ
Первый шарик бросаем последовательно с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 и 100 этажей. Если на каком-то из этих этажей шарик разбивается, то второй шарик начинаем бросать с этажа, который на один выше, чем был на предыдущем шаге. Если второй шарик не разбивается, то поднимаемся вверх на один этаж. И так далее пока второй шарик не разобьётся. Этаж на котором разобьётся второй шарик и будет искомым. Например, бросаем первый шарик с 14-го этажа - не разбивается, бросаем его же с 27-го этажа - разбивается, тогда второй шарик начинаем бросать с 15-го (14+1) этажа, с 16-го, с 17-го и т.д. пока не разобьётся. Максимальное количество попыток при таком подходе 14.

И ещё - головоломка про радиоактивность.

14 комментариев:

  1. два, один с первого второй с последнего?

    ОтветитьУдалить
    Ответы
    1. Допустим первый шарик остался целым, второй разбился. Как мы определим самый низкий этаж, с которого шарик начинает разбиваться?

      Удалить
    2. ну тогда кидаем с 1-ого не разбился, поднимаемся на 3-ий кидаем, если разбился кидаем с 2-го, если не разбился поднимаемся на 5-ый и так далее.
      Но только это всё относительно, так как раз на раз не приходится.

      Удалить
    3. Для этого алгоритма худший случай когда шарик разбивается на 99 этаже. Потребуется 50 попыток. Есть более оптимальные варианты.

      Удалить
  2. Понимание динамического программирования и одного состояния (хранить в линейном массиве).

    Мне нравится вариация (http://neerc.ifmo.ru/school/archive/2005-2006.html#team-rus задача H.), Количество шариков лежит в интервале от 1 до 6. Не разбившиеся объекты можно поднять с земли. Нужно минимизировать количество подъемов вверх по этажам (спуски вниз за неразбившимися шариками не учитываются, подниматься вверх - тяжело).

    Собственно, тоже динамическое программирование. Но состояние будет 5-ти-мерным.

    ОтветитьУдалить
    Ответы
    1. Тут учитывается только количество попыток. Подъёмы и спуски не берём в расчёт. Так какой же ответ?

      Удалить
  3. честно не вычислял, но логика примерно така если с 50-го кидать
    то можно залететь на 50+1 попытку = 51
    с 20-го, то 5+19 = 24 и т.д.
    вобщем с 10 -го если кидать
    получается где то 10+8 попыток = 18раз. То есть кинули с 10 го разбился. Еще 8 попыток, начиная со 2-го этажа и если разобьется на 9-ом этаже. Если на 10-м не раблися то с 20-го кидаем и в случае разрушения, кидаем 2-ой с 12-го. Если, гад, бьется на 99-ом, то 18 попыток.

    ОтветитьУдалить
    Ответы
    1. Есть вариант с ещё меньшим количеством попыток.

      Удалить
  4. тааак...
    кидаем с 15(можем попасть на 13+1 попыток в случае разбиения)
    кидаем с 30(15 попыток)
    кидаем с 45(16 попыток можем получить)
    кидаем с 55(на 9+3 попыток)
    кидаем с 65(13 попыток)
    кидаем с 75(14)
    кидаем с 85(15)
    кидаем с 95(16)
    кидаем с 100(4+7 = 11 попыток)

    итого максимально могли получить 16 попыток при таком способе

    ОтветитьУдалить
  5. Ошибочка на 95 этаже 17 попыток. Вобщем 17 конечный ответ.

    ОтветитьУдалить
  6. если с 14-го, то чтобы не увеличить количество попыток в дальнейшем будем уменьшать каждый раз шаг!
    1 бросок с 14 го этажа, если разбили то 13+1 попытка
    потом с 27 этажа, если разбили то 2 + 12 попытка
    39 то 3+11 попыток
    50 этаж
    60
    69
    77
    84
    90
    95
    99 - если вдруг разбивается с 99-го то 11 попыток вообще
    если 100 - то 12.
    При таком раскладе за 14 можно уложиться.
    возможно такое линейное увеличение не оптимально, может надо как то шаг оптимизировать...
    или просто какой то подвох!
    физика задействована типа gt^2/2 ?

    ОтветитьУдалить
  7. как не крути - но попыток только 13

    ОтветитьУдалить