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

Цитата (bergerug @ 7.02.2015 - 13:30)

Цитата (tserg @ 7.02.2015 - 12:27) У тебя 100 бросков получается. Задача - минимизировать количество бросков Не 100 а от 1 до 100. Может быть и 1.

А может быть и 100. Не быть тебе проектировщиком - самый худший вариант не учитываешь. Короче тут надо дойти до ста, наименее коротким способом.

Учитывая, что все вычисления яповцев основываются на падении с максимально возможной высоты в сто этажей - можно сделать вывод что они что то знают. Значит можно быть самым хитрожопым и просто кинуть с сотого этажа. Одной попыткой. И он разобьётся.

10, 23. 35, 46, 56, 65, 73, 80, 86, 91, 95, 98, 100
11, 24, 36, 47, 57, 66, 74, 81, 87, 92, 96, 99, 100
12, 25, 37, 48, 58, 67, 75, 82, 88, 93, 97, 100
13, 26, 38, 49, 59, 68, 76, 83, 89, 94, 98, 100
Итого в худшем случае имеем 14 бросков. (Что делать, если шарик разбился на каком-то этапе, уже много раз объяснено выше)
Это сообщение отредактировал rrkalimullin - 7 фев 2015 в 13:44

Цитата (tserg @ 7.02.2015 - 15:19)

я гарантированно за 20 падений могу узнать точный этаж. У кого есть какой-нибудь гарантированный алгоритм (порядок действий), чтобы можно было узнать этот этаж и не сдохнуть от беготни по этажам?

Ну не 20, а 19, это раз. А во вторых - лифт решает

Цитата

Вот что пятница делает... мозг только хуйню про 51 придумал:)

Чел... Ты это... Присядь... Суббота сегодня...

Цитата (YavorOcelot @ 7.02.2015 - 13:16)

Кидаем с 50 этажа.(первый раз) Кидаем с 25 или 75 этажа.(второй раз) Кидаем с 13,36,63,87 этажа.(третий раз) Кидаем с 6,18,28,42,57,69,81,93 этажа(четвёртый раз) Кидаем с 3,9,15,21,26,31,39,45,54,60,78,90.(пятый раз) Ну а на шестой чисто для проверки.Всё.

А если должен разбиться на 29м этаже?

Кидаем так.
19
36
51
64
75
84
91
96
99
100
Итого минимум 10 попыток чтобы дойти до 100 этажа.
Плюс к этому количество попыток между этими этажами. А это максимум 18. (Исследовать интервал 1-18). Итого 19 попыток достаточно. Если первый разбивается с 19. В остальных случаях попыток нужно меньше.
Ответ макс число 19. Есть кто доказал меньшее?

ну, за 20 - просто. кидать шарики с шагом 10, т.е. 10, 20, 30... дальше от разбившегося у тебя еще 10 попыток.

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

Цитата (rrkalimullin @ 7.02.2015 - 16:37)

11, 24, 36, 47, 57, 66, 74, 81, 87, 92, 96, 99 Итого в худшем случае имеем 14 бросков.

Тоже вариант этот встречал. Но гарантированного результата он не даст.
Идешь на 11 этаж, кинул - разбился. Идешь на 10, кинул - разбился. Дальше чо?)

Боже, сколько чукчей нечитателей! Лишь бы ляпнуть, 51, 20, 19 попыток. Тыщу раз сказали правильный ответ 14 попыток!

А я таки ещё позанудствую с условием задачи - этажи как считать? Как у нас или как в Европе? В Европе первый - это наш второй .
То есть сколько окон на фасаде - 100 или 101?
Лестничных пролётов - 99 или 100?
Это важно !
Хотя, я шучу. Я ещё думаю.
п.с. Мне очень нравятся такие загадки, но Яп под них технически не заточен. Они как правило съезжают в инке.

Цитата (Serrega @ 7.02.2015 - 13:44)

Цитата (rrkalimullin @ 7.02.2015 - 16:37) 11, 24, 36, 47, 57, 66, 74, 81, 87, 92, 96, 99 Итого в худшем случае имеем 14 бросков. Тоже вариант этот встречал. Но гарантированного результата он не даст. Идешь на 11 этаж, кинул - разбился. Идешь на 10, кинул - разбился. Дальше чо?)

идешь не на 10 а на первый и вверх потом!

19 попыток у меня получилось.

Кидаем через 10 этажей первый шар. Разбился на 80-м, значит спускаемся на 70-й и кидаем последовательно до искомого. Максимум получится 19 попыток. (1-я-10 этаж,2-я -20 этаж,3-я -30 этаж,4-я -40 этаж,5-я -50 этаж,6-я -60 этаж,7-я -70 этаж,8-я -80 этаж,9-я -90 этаж,10-я -100 этаж, 11-я - 91 этаж,12-я -92 этаж,13-я -93 этаж,14-я -94 этаж,15-я -95 этаж,16-я -96 этаж,17-я -97 этаж,18-я -98 этаж,19-я -99 этаж.

Цитата (Serrega @ 7.02.2015 - 15:44)

Цитата (rrkalimullin @ 7.02.2015 - 16:37) 11, 24, 36, 47, 57, 66, 74, 81, 87, 92, 96, 99 Итого в худшем случае имеем 14 бросков. Тоже вариант этот встречал. Но гарантированного результата он не даст. Идешь на 11 этаж, кинул - разбился. Идешь на 10, кинул - разбился. Дальше чо?)

Слова "чо" в русском языке нет.
В случае разбивания на 11 этаже. имеем варианты
11, 1 - 2 броска
11, 1, 2 -3 броска
11, 1, 2, 3 - 4 броска
11, 1, 2, 3, 4 -5 бросков
11, 1, 2, 3, 4, 5 - 6 бросков
11, 1, 2, 3, 4, 5, 6 - 7 бросков
11, 1, 2, 3, 4, 5, 6, 7 - 8 бросков
11, 1, 2, 3, 4, 5, 6, 7, 8 - 9 бросков
11, 1, 2, 3, 4, 5, 6, 7, 8, 9 - 10 бросков
11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 - 11 бросков
Это сообщение отредактировал rrkalimullin - 7 фев 2015 в 13:49

Цитата (tserg @ 7.02.2015 - 11:32)

Цитата (MAPT @ 7.02.2015 - 12:32) 50->25->12->6->3-> 2(если оба разбились на 3-ем) или 4 (если не разбились) Итого: до 6 попыток в идеале. У тебя всего 2 шара!!!

Тогда тупизм в условии - если всего два шара = две попытки, зачем спрашивать кол-во попыток?
Получается их всего две?

А если нет - то зачем уточнять что шара всего два?

Добавлено в 13:51

Цитата (alextruvorfo @ 7.02.2015 - 12:45)

Боже, сколько чукчей нечитателей! Лишь бы ляпнуть, 51, 20, 19 попыток. Тыщу раз сказали правильный ответ 14 попыток!

Согласен - 10 попыток чтоб исследовать десятки и максимум четыре чтоб выяснить этаж в пределах 1-9 внутри десятка
Это сообщение отредактировал gogenzolern - 7 фев 2015 в 13:48

Цитата (tserg @ 7.02.2015 - 13:26)

Цитата (dinozavr2000 @ 7.02.2015 - 12:22) Начинай с сотого. Вопрос был: какой алгоритм бросков, чтобы минимизировать их количество

Это типичная задача на поиск в отсортированном массиве))))
Это сообщение отредактировал Калликанзар - 7 фев 2015 в 13:54

Цитата

Тоже вариант этот встречал. Но гарантированного результата он не даст. Идешь на 11 этаж, кинул - разбился. Идешь на 10, кинул - разбился. Дальше чо?)

А религия не позволяет после 11 идти на первый?

Цитата (gogenzolern @ 7.02.2015 - 15:48)

максимум четыре чтоб выяснить этаж в пределах 1-9 внутри десятка

Это каким образом?

Элементарно! 100/n=n или 100=n2 или n=sqrt(100)= 10

Идем на 10 этаж. Если не разбился, то на 20, 30 итд...
Если разбился - спускаемся на начало этого десятка и перебираем вверх все этажи, пока шарик не разобьется! Итого максимум киданий будет 10 (десятков) + 10 (в 1 десятке) = 20 включая предел - крышу!

Хотя, если взять экспоненту?
Допустим первый этаж возьмем от 10 (оптимпльного) до 20 (максимального без решения). Так с каждым оценочным броском количество этажей уменьшается а броски увеличиваются, то можно принять эти величины равными, а значит первоначальный этаж будет 15.

получается
Этап. Этаж -- броски(оценочный/результирующий)
1. 15 -- 1+14 = 15
2. 29 -- 2+13 = 15
3. 42 -- 3+12 = 15
4. 54 -- 4+11 = 15
5. 63 -- 5+10 = 15
6. 73 -- 6+9 = 15
7. 82 -- 7+8 = 15
8. 90 -- 8+7 = 15
9. 98 -- 9+6 = 15

Остается еще 2 этажа - а это 2 броска. Тут немного ошиблись ввиду дискретных величин. Но если первоначальный шаг делать с 16 этажа, то гарантировано можно предполагать, что задачу выполним за 16 бросков!

Этап. Этаж -- броски(оценочный/результирующий)
1. 16 -- 1+15 = 16
2. 31 -- 2+14 = 16
3. 45 -- 3+13 = 16
4. 58 -- 4+12 = 16
5. 70 -- 5+11 = 16
6. 81 -- 6+10 = 16
7. 91 -- 7+9 = 16
8. 100 -- 8+8 = 16
Это сообщение отредактировал Berdisheff - 7 фев 2015 в 14:39

Цитата

Слова "чо" в русском языке нет. В случае разбивания на 11 этаже. имеем варианты 11, 1 - 2 броска 11, 1, 2 -3 броска 11, 1, 2, 3 - 4 броска 11, 1, 2, 3, 4 -5 бросков 11, 1, 2, 3, 4, 5 - 6 бросков 11, 1, 2, 3, 4, 5, 6 - 7 бросков 11, 1, 2, 3, 4, 5, 6, 7 - 8 бросков 11, 1, 2, 3, 4, 5, 6, 7, 8 - 9 бросков 11, 1, 2, 3, 4, 5, 6, 7, 8, 9 - 10 бросков 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 - 11 бросков

Это не является максимумом. Ибо он вообще может не разбиться. Вы почему не учитываете?

Цитата (gogenzolern @ 7.02.2015 - 13:48)

Цитата (tserg @ 7.02.2015 - 11:32) Цитата (MAPT @ 7.02.2015 - 12:32) 50->25->12->6->3-> 2(если оба разбились на 3-ем) или 4 (если не разбились) Итого: до 6 попыток в идеале. У тебя всего 2 шара!!! Тогда тупизм в условии - если всего два шара = две попытки, зачем спрашивать кол-во попыток? Получается их всего две? А если нет - то зачем уточнять что шара всего два? Добавлено в 13:51 Цитата (alextruvorfo @ 7.02.2015 - 12:45) Боже, сколько чукчей нечитателей! Лишь бы ляпнуть, 51, 20, 19 попыток. Тыщу раз сказали правильный ответ 14 попыток! Согласен - 10 попыток чтоб исследовать десятки и максимум четыре чтоб выяснить этаж в пределах 1-9 внутри десятка

Неразбившийся шар можно поднять и кинуть еще раз и это ПОПЫТКА!
Не десятки надо разбивать, а 14,27,39,50,60,69,77,84,90,95,99

Цитата (hotaby4 @ 7.02.2015 - 12:37)

Первый кидаем от 1 до 100 с шагом 10. Если разбился - кидаем второй от последней десятки с шагом 1. Итог 20 max.

вышло по твоему методу 19!!!

Цитата (Gooph @ 7.02.2015 - 15:54)

Цитата Слова "чо" в русском языке нет. В случае разбивания на 11 этаже. имеем варианты 11, 1 - 2 броска 11, 1, 2 -3 броска 11, 1, 2, 3 - 4 броска 11, 1, 2, 3, 4 -5 бросков 11, 1, 2, 3, 4, 5 - 6 бросков 11, 1, 2, 3, 4, 5, 6 - 7 бросков 11, 1, 2, 3, 4, 5, 6, 7 - 8 бросков 11, 1, 2, 3, 4, 5, 6, 7, 8 - 9 бросков 11, 1, 2, 3, 4, 5, 6, 7, 8, 9 - 10 бросков 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 - 11 бросков Это не является максимумом. Ибо он вообще может не разбиться. Вы почему не учитываете?

Дядя, вы дурак?
Читайте внимательнее.
Это сообщение отредактировал rrkalimullin - 7 фев 2015 в 13:55

Цитата (gogenzolern @ 7.02.2015 - 13:48)

Цитата (tserg @ 7.02.2015 - 11:32) Цитата (MAPT @ 7.02.2015 - 12:32) 50->25->12->6->3-> 2(если оба разбились на 3-ем) или 4 (если не разбились) Итого: до 6 попыток в идеале. У тебя всего 2 шара!!! Тогда тупизм в условии - если всего два шара = две попытки, зачем спрашивать кол-во попыток? Получается их всего две? А если нет - то зачем уточнять что шара всего два?

Надо испульзуя всего 2 шара, выяснить на каком этаже они начнут разбиваться.
Гипотетически шарики могут разбиться на любом этаже.
Если вы кинули с 50->25, и они разбились, то вы разбили оба шара, но так и не узнали ответ.

Я сделаю за 18 попыток максимум!
Первая- с десятого,разбился-перебираем с первого,десять вариантов
Вторая- с двадцатого,алгоритм как у первой попытки
.
.
.на сотый даже не поднимусь,начну с девяностого.девять декад+девять этажей=18 попыток!

Цитата (Serrega @ 7.02.2015 - 13:44)

Цитата (rrkalimullin @ 7.02.2015 - 16:37) 11, 24, 36, 47, 57, 66, 74, 81, 87, 92, 96, 99 Итого в худшем случае имеем 14 бросков. Тоже вариант этот встречал. Но гарантированного результата он не даст. Идешь на 11 этаж, кинул - разбился. Идешь на 10, кинул - разбился. Дальше чо?)

Идешь не на 10-й а на первый и снизу ищешь этаж в этом диапазоне.