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

Можно сделать за 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 бросков.

Цитата (rrkalimullin @ 7.02.2015 - 15:50)

Есть ещё другой вариант. Бывает откроешь 10-15 тем без комментариев... А когда откомментировал - смотришь, твой комментарий уже на 7-й странице.

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

Теперь необходимо продвинуться в решении дальше - доказать, что за 13 бросков решить задачу не получится.
Это сообщение отредактировал rrkalimullin - 7 фев 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. Есть, правда, еще тут одна неочевидная деталь в решении, но пока о ней умолчу.

Цитата (Серенький @ 7.02.2015 - 17:56)

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

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



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

Цитата (Серенький @ 7.02.2015 - 17:56)

Коллеги, разрешите представить своё решение. Первый этаж, с которого бросать шарик (пусть это будет 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. Есть, правда, еще тут одна неочевидная деталь в решении, но пока о ней умолчу.

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

Цитата

Цитата (Серенький @ 7.02.2015 - 17:56) Т.е. при n от 8 до 13 нам потребуется 19 шагов. Далее кол-во шагов будет возрастать. P.S. Есть, правда, еще тут одна неочевидная деталь в решении, но пока о ней умолчу. Именно, но если я где-то тупонул в построении - уточните переделаю! Давайте свою неоднозначную деталь То есть если кидать через 14 этажей (до разбития первого шара), то самый "фиговый" 91 этаж.

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

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

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

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

Цитата (Серенький @ 7.02.2015 - 17:56)

0. Бросаем первый шар с n-го этажа. 1. Если первый шар шар разбился, то переходим на n-1 этаж вниз и бросаем с каждого этажа с шагом 1, перемещаясь вверх. И находим нужный этаж. 2. Если шар не разбился, то поднимаемся на n этажей вверх и бросаем первый шар опять. Далее переходим к п.1

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

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

Цитата

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

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

Цитата

И правда, нет смысла кидать с шагом фиксированным, ибо тогда на первых шагах остается дофига неиспользованных попыток :) Каждый следующий шаг можно уменьшать на 1. Итого имеем: Пусть гарантированный минимум это X. Первый бросок с шагом X с этажа X, второй с шагом X-1 с этажа 2X-1, третий с шагом X-2 c этажа 3X-3 и так далее в общем случае k-й бросок (начинаем с k=0) будет с шагом X-k с этажа (k+1)*X-k*(k+1)/2, при этом шаг X=k уже не имеет смысла. Надо найти такое минимальное X, чтобы (X+1)*X-X*(X+1)/2=X*(X+1)/2 всё еще было не менее 100. Считаем X*(X+1)/2=100 => X*X+X-200=0, один из корней - X=13.6 округлим до целого и итого имеем X=14. Первый шар бросаем на 14 этаж, потом на 14+13=27 этаж, потом на 27+12=39 этаж, потом на 39+11=60 этаж, потом на 60+9=69 этаж, потом на 69+8=77 этаж, потом на 77+7=84 этаж, потом на 84+6=90 этаж, потом на 90+5=95 этаж, потом на 99 этаж. Если бы начинали бросать с 13 этажа, до 100 этажа бы не дошли.

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

Цитата (WhiskIn @ 7.02.2015 - 19:53)

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

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


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

Цитата

Цитата (Серенький @ 7.02.2015 - 17:56) 0. Бросаем первый шар с n-го этажа. 1. Если первый шар шар разбился, то переходим на n-1 этаж вниз и бросаем с каждого этажа с шагом 1, перемещаясь вверх. И находим нужный этаж. 2. Если шар не разбился, то поднимаемся на n этажей вверх и бросаем первый шар опять. Далее переходим к п.1 Не работает. Примем n=14 (этаж. с которого начинаем бросать) Бросаем Шар разбился Переходим на этаж ниже (n-1=13) Бросаем Шар разбился Всё, шаров больше нет. Так что алгоритм буксанул уже на шаге 1.

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

Цитата

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

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

Цитата (Серенький @ 7.02.2015 - 20:07)

Цитата Цитата (Серенький @ 7.02.2015 - 17:56) 0. Бросаем первый шар с n-го этажа. 1. Если первый шар шар разбился, то переходим на n-1 этаж вниз и бросаем с каждого этажа с шагом 1, перемещаясь вверх. И находим нужный этаж. 2. Если шар не разбился, то поднимаемся на n этажей вверх и бросаем первый шар опять. Далее переходим к п.1 Не работает. Примем n=14 (этаж. с которого начинаем бросать) Бросаем Шар разбился Переходим на этаж ниже (n-1=13) Бросаем Шар разбился Всё, шаров больше нет. Так что алгоритм буксанул уже на шаге 1. Если бы вы читали внимательно алгоритм, то увидели бы, что там написано "переходим на n-1 этаж вниз", а не "переходим на n-1-й этаж". Цитата Тут уже сто раз приводили решение, что вы велосипед-то всё изобретаете? :) 14 попыток нужно. 14. Ваша ошибка в том, что шаг переменным должен быть, а у вас постоянный. Да, вы правы, именно в этом моя ошибка, что не стал решать в общем виде. Однако, когда я смотрел тему, в ней так и не увидел решения. Видимо, оно появилось когда я писал свой пост.

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

Цитата

Тут уже сто раз приводили решение, что вы велосипед-то всё изобретаете? :) 14 попыток нужно. 14. Ваша ошибка в том, что шаг переменным должен быть, а у вас постоянный. Да, вы правы, именно в этом моя ошибка, что не стал решать в общем виде. Однако, когда я смотрел тему, в ней так и не увидел решения. Видимо, оно появилось когда я писал свой пост. Если Вы его писали в течении 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 фев 2015 в 20:29

Цитата (crugiada @ 7.02.2015 - 20:07)

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

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

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

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

Цитата (Одинец @ 13.01.2011 - 10:24)

Плюсую. Три года со всеми нашими кандидатами (отдел главного энергетика) собеседование по технической части проводил я. И старался напугать новичка (а то трое не дожили до конца испытательного срока). Главный энергетик после двоих удравших прямо с собеседования очень попросил не пугать... Картина маслом. У нас остался единственный на тот момент выживший электрик. Без допуска на высоту. Нам надо в ангаре - складе развесить 14 здоровенных светильников с лампами ДНАТ-250. Причём срочно. А ангар успели отменно захламить - про леса сразу забудь. Ну я всё же инженер, а не промоутер. Одел робу (тогда мне была не положена, но имелась), пояс монтажника-высотника со страховкой - и принялся изображать "человека-паука", лазая по внутренним решётчатым фермам. Зафиксируюсь на верхотуре (примерно 12-14 метров), свешиваю вниз конец, электрик на него вешает заряженный светильник, втягиваю, вешаю, провод в гофре от него по ферме до стены. А там уже соединительные коробки. роба, конечно, вся в пыльной саже и паутине. Срабатывает напоминалка на сотовом, спускаюсь, мою руки и лицо и иду на вахту. Как есть - в робе, в поясе, со страховочным концом через плечо и свисающим с него карабином... Провожу новичка и говорю ему, что меня настоятельно просили его не пугать и прошу угадать мою должность. Он, заметив под робой рубашку с галстуком, уверенно говорит "Бригадир высотников". Нет, говорю, инженер-энергетик (он на ту же вакансию). Не испугался...

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

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

Цитата (derfox @ 14.04.2012 - 10:36)

Можно еще сделать 2 разреза как обычно, а последний поперек торта.

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