Вопросы на собеседовании

Можно сделать за 19 бросков.
Начинаем с 9 и т.д с шагом 10.
Получается 9 19 29 39 49 59 69 79 89 99 =10 бросков. Если не разбился, то ответ 100 этаж.
Допустим разбился на 99. Тогда начинаем бросать с 90 с шагом 1.
получается 90 91 92 93 94 95 96 97 98= 9 бросков.

Бывает и так. Но ведь обновить страничку, когда к ней наконец доберешься - необходимо.
Эк тебя "нечитаки" заминуcовали. Поправил :)

Теперь необходимо продвинуться в решении дальше - доказать, что за 13 бросков решить задачу не получится.

Это сообщение отредактировал rrkalimullin - 7.02.2015 - 16:47

Стоим внизу сначала подкидываем шарик до второго этажа, смотрим, разбился не разбился, потом до третьго и .... Пока не разобьется, бред конечно, но хоть бегать по этажам не придется))
А вообще мне больше всех понравился вариант, предложенный выше, где кидают с каждого четного этажа.

Коллеги, разрешите представить своё решение.
Первый этаж, с которого бросать шарик (пусть это будет n), на первый взгляд можно выбрать произвольно, однако, шарик может разбиться уже с 1-го падения.
Посему нам придется проверять все нижележащие этажи начиная с самого нижнего (n-1 шагов). С другой стороны, если шарик не разбился, то перед нами встает задача про (100-n) этажное здание и 2 шара.

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

Рассмотрим бросание первого шара начиная с этажа n с шагом n, т.е. n, 2*n, ..., n*k, где k=[100/n] - целая часть от 100/n. При этом алгоритм бросания такой:
0. Бросаем первый шар с n-го этажа.
1. Если первый шар шар разбился, то переходим на n-1 этаж вниз и бросаем с каждого этажа с шагом 1, перемещаясь вверх. И находим нужный этаж.
2. Если шар не разбился, то поднимаемся на n этажей вверх и бросаем первый шар опять. Далее переходим к п.1

Нетрудно видеть, что самый "плохой" вариант, это когда мы доходим до этажа n*k, шар разбивается, и мы затем проверяем еще n-1 этаж с прошлого кидания первого шара. Итого шагов, гарантированно приводящих к решению задачи будет:

N=[100/n]+n-1

Найдем минимум этой функции:
n N
1 100
2 51
3 35
4 28
5 24
6 21
7 20
8 19
9 19
10 19
11 19
12 19
13 19
14 20
15 20
16 21

Т.е. при n от 8 до 13 нам потребуется 19 шагов.
Далее кол-во шагов будет возрастать.

P.S. Есть, правда, еще тут одна неочевидная деталь в решении, но пока о ней умолчу.

Именно, но если я где-то тупонул в построении - уточните переделаю!
Давайте свою неоднозначную деталь
То есть если кидать через 14 этажей (до разбития первого шара), то самый "фиговый" 91 этаж.


Это сообщение отредактировал crugiada - 7.02.2015 - 18:32

Абсолютно согласен. Получил тот же результат. Можно составить функцию от x и исследовать её на минимум или же для наглядности рассчитать всё в электронной таблице - результат одинаковый. При шаге от 8 до 13 максимальное количество попыток гарантирующее ответ - 19.

Самый "фиговый" этаж это 98-й, до которого мы доберемся на 7-м шаге.
И "фигово" то, что если на этом шаге шар разбивается и нам приходится выяснять по алгоритму выше, что нужный этаж, на самом деле 97-й. Т.е. сделать еще 13 шагов начиная с 84-го. А всего 7+13=20.

"Неочевидная" деталь это то, что алгоритм (шаг) неизменен, если первый шар не разбивается. И, насколько я уже выяснил после перемещения этой темы, это приводит к тому, что есть решение лучше.

Самое обидное, что мой первый ответ в этой ветке заминусили, причем не открывая уже шпалят. А ведь там был не такой уж плохой вариант, жалко, что не на 2 шарика.
Кстати, если бы шариков было 3, то мы бы тут горла поперегрызали, я думаю, пока бы дошли до правильного ответа — 9.

Вот ещё перерисовал для шага в 8 этажей.
(у меня с геометрией всегда было лучше чем с алгеброй)
И ответ 19 правильный, но в начале кто-то "папугал" всех формулами, и хомяки уважаемые пользователи Япа забрасывали всех ссаными тряпками минусами у кого было не "14". Демократия - чё.

Не работает.
Примем n=14 (этаж. с которого начинаем бросать)
Бросаем
Шар разбился
Переходим на этаж ниже (n-1=13)
Бросаем
Шар разбился
Всё, шаров больше нет.
Так что алгоритм буксанул уже на шаге 1.
Первый шар разбился на 14-м, второй на 13-м. Всё, что мы выяснили - шары нельзя бросать выше, чем с 13 этажа. А с 12-го можно? А с 11-го? А с 1-го? А х.з, шаров-то больше нет

Тут уже сто раз приводили решение, что вы велосипед-то всё изобретаете? :)
14 попыток нужно. 14.
Ваша ошибка в том, что шаг переменным должен быть, а у вас постоянный.

Это сообщение отредактировал WhiskIn - 7.02.2015 - 20:01

Самое обидное - то что правильный ответ дан ещё семь часов назад.

и повторен ещё пару раз. На восьмой странице темы

Ой, всё!
Ткните пожалуйста носом в пост где конкретно расписано по этажам или "переменность" шага. Хочу таки изобразить графически именно самый "плохой" (крайний) вариант?
упд. всё увидел.
упд2. Одна картинка заменяет 10000 слов © конфуций (кажись)
то есть самый плохой вариант 98 этаж(по пробегу, а не попыткам - это я щас с собой разговариваю).

Это сообщение отредактировал crugiada - 7.02.2015 - 21:06

Если бы вы читали внимательно алгоритм, то увидели бы, что там написано "переходим на n-1 этаж вниз", а не "переходим на n-1-й этаж".

Да, вы правы, именно в этом моя ошибка, что не стал решать в общем виде.
Однако, когда я смотрел тему, в ней так и не увидел решения. Видимо, оно появилось когда я писал свой пост.

Если Вы его писали в течении 5 часов, возможно, что и так.
Первый правильный ответ (14) появился около часу дня.
И еще. n же у нас может быть равным 2, к примеру. Вот и получается, что переходим на n-1 ;), то бишь на 13-й. Неоптимально.
Где-то странице на 5-6-7 раскладывали всё.

Если бы вы читали внимательно алгоритм, то прочитали бы это:
==
Рассмотрим бросание первого шара начиная с этажа n с шагом n, т.е. n, 2*n, ..., n*k, где k=[100/n] - целая часть от 100/n. При этом алгоритм бросания такой:
==
В таком случае при n=2 мы бы получили после 2 этажа (если орех разбился), проверку первого этажа. А при разбитии ореха на 7 шаге на 14 этаже получили бы проверку 13-го этажа при условии, что на 12-м орех не разбился.

P.S. Тема называлась по-другому. На первых трёх и последних трёх страницах не нашел решений и ссылки на них. Значит мне и тут не повезло :)

Это сообщение отредактировал Серенький - 7.02.2015 - 20:29

Ну вот и всё, тему можно закрывать. В любом виде, как в графическом, так и в математическом, получилось 14 попыток :)

— Если бы вы могли быть любым супергероем, кто бы это мог быть? — AT & T.
Мой ответ Александр Белл.
Я принят в AT&T?

Да, даже на чисто практическом уровне это выглядит логично - уменьшать шаг на количество использованных попыток. Сразу в голову не пришло. Хорошая задача.

Бро, ты как всегда, окуенен!
Надо до кучи ещё напугать единственного оставшегося электрика без допуска на высоту , чтоб он благополучно ушёл к другому работодателю, где не принято прямо с порога гнуть пальцы пугать соискателей.
Вам же нужны именно "шашечки, а не ехать".
Посему, Ваша перспектива- одевать смокинг под телогреечку и лазить по верхотуре за себя и того парня.
Работа пыльная, но зато в глазах вышестоящего начальства - Вы не попадёте под сокращение.
Надеюсь, новый соискатель не ужился в настоящем дружном коллективе, где понты дороже денег и также нашёл адекватную работу с более менее вменяемым начальством.

Добавлено в 15:36

Про этот алгоритм догадался сразу же.
Но как быть, если сверху на торте кремовые розочки? (на дне их же нет).
А куски должны быть одинаковые (ну или близко- равноценные)
Каждый при делёжке будет стараться взять "вершки", считая их вкуснее "корешков"