Неприятная задачка на интервью

Leo Gan · Сообщение **Leo Gan** » 30 май 2007, 23:37

папа Карло писал(а):
Leo Gan писал(а):что там получается? 33 цикла. или 32 или 34?
15

"Берешь первый шарик. Бросаешь с 14ого этажа. Если разбивается, вторым проверяешь 1, 2, 3, ..., 13. Максимум 14 раз. Если с 14 не разбился, бросаешь с 14+13 = 27. Разбивается, вторым проверяешь 12 этажей 15, 16, ..., 26. Итого опять 14 раз бросили. Если с 27ого не разбился, проверяешь 14+13+12 = 39. Ну и так далее."

тогда уж 14

, т.к. "Бросаешь с 14ого этажа. Если разбивается, вторым проверяешь 1, 2, 3, ..., 13. Максимум 14 раз" - надо 1,2,3..12 Больше уже не надо. Разбился - значит 12, не разбился - значит 13. Граничные условия, однако

Alexandr · Сообщение **Alexandr** » 30 май 2007, 23:48

На 13 может и не разбиться

Leo Gan · Сообщение **Leo Gan** » 31 май 2007, 08:20

Alexandr писал(а):На 13 может и не разбиться

так 14 уже разбился.

aissp · Сообщение **aissp** » 31 май 2007, 08:41

Пральный ответ (ну или тот который у меня получился)

int n = sqr(2*N);

где n ето размер первого отрезка (етаж с которого первый раз бросаем) а N етажность здания. Заодно доказывается что за меньшее число бросков низзя

папа Карло

Leo Gan писал(а):
Alexandr писал(а):На 13 может и не разбиться
так 14 уже разбился.

не бросив с 13го этажа ты не будешь знать... разбивается он на 13ом или 14ом (где лдин шарик уже разбился).

Stanislav · Сообщение **Stanislav** » 31 май 2007, 09:32

aissp писал(а):Пральный ответ (ну или тот который у меня получился)
int n = sqr(2*N);
где n ето размер первого отрезка (етаж с которого первый раз бросаем) а N етажность здания. Заодно доказывается что за меньшее число бросков низзя

Для маньяков хрустальных шариков: А если имеется m хрустальных шариков?

tma · Сообщение **tma** » 31 май 2007, 09:37

Дима писал(а):Ссылку эту видел По-моему, она не совсем не совсем соответствует задаче Пытаюсь разрезать карточки. Пока квадрата со стороной корень из 15-ти не получается Юрий, под широкими концами треугольника ты имел ввиду гипотенузу или бОльший катет ? И резать под прямым углом ?

Отмерить длину, равную корню из 15 получилось так:
египедский прямоугольный треугольник имеет стороны 3-4-5, на двух прямоугольниках имеем 3 и 5.
Положите первый прямоугольник на второй сверху и, придерживая один угол вместе, начинайте вращать второй прямоугольник против часовой стрелки на примерно 30 градусов до соприкосновения вершины первого со стороной второго. На просвет можно видеть, как сторона нижнего прямоугольника стала гипотенузой треугольника 3-4-5. Таким образом, отметили длину, равную 1. Т.е. прямоугольники размечены.
Дальше можно отметить длину, равную корню из 15, так. Гипотенуза прямоугольного треугольника со сторонами 1 и 1 =корню из 2.
Гипотенуза прямоугольного треугольника, построенного на катетах корень из 2 и 2, равна корню из 6.
Гипотенуза прямоугольного треугольника, построенного на катетах корень из 6 и 3, равна корню из 15.
Т.е. имеем корень из 15.

aissp · Сообщение **aissp** » 31 май 2007, 09:38

И зачем ты ето сказал? У меня в планах два документа написать поругаться с ку аем и попытаться пофиксить чужую багу. Теперь планы коту под хвост?

Ан нет не очень сложно

int n = sqrt(2*N/(m-2)) где то так

ura · Сообщение **ura** » 31 май 2007, 10:02

aissp писал(а):И зачем ты ето сказал? У меня в планах два документа написать поругаться с ку аем и попытаться пофиксить чужую багу. Теперь планы коту под хвост?

Ан нет не очень сложно

int n = sqrt(2*N/(m-2)) где то так

m - это что?

aissp · Сообщение **aissp** » 31 май 2007, 10:06

Да тут Станислав поставил задачу прально:) N - этажность дома m - количество щариков... в последнем ответе n+m-2 дает минимальное количество бросков...

ura · Сообщение **ura** » 31 май 2007, 10:07

tma писал(а):
Дима писал(а):Ссылку эту видел По-моему, она не совсем не совсем соответствует задаче Пытаюсь разрезать карточки. Пока квадрата со стороной корень из 15-ти не получается Юрий, под широкими концами треугольника ты имел ввиду гипотенузу или бОльший катет ? И резать под прямым углом ?
Отмерить длину, равную корню из 15 получилось так:
египедский прямоугольный треугольник имеет стороны 3-4-5, на двух прямоугольниках имеем 3 и 5.
Положите первый прямоугольник на второй сверху и, придерживая один угол вместе, начинайте вращать второй прямоугольник против часовой стрелки на примерно 30 градусов до соприкосновения вершины первого со стороной второго. На просвет можно видеть, как сторона нижнего прямоугольника стала гипотенузой треугольника 3-4-5. Таким образом, отметили длину, равную 1. Т.е. прямоугольники размечены.
Дальше можно отметить длину, равную корню из 15, так. Гипотенуза прямоугольного треугольника со сторонами 1 и 1 =корню из 2.
Гипотенуза прямоугольного треугольника, построенного на катетах корень из 2 и 2, равна корню из 6.
Гипотенуза прямоугольного треугольника, построенного на катетах корень из 6 и 3, равна корню из 15.
Т.е. имеем корень из 15.

Мда, сразу видно, что интервьюирующий в детстве по улицам не шастал, а читал Юный Техник.

Stanislav · Сообщение **Stanislav** » 31 май 2007, 10:15

aissp писал(а):И зачем ты ето сказал? У меня в планах два документа написать поругаться с ку аем и попытаться пофиксить чужую багу. Теперь планы коту под хвост?
Ан нет не очень сложно
int n = sqrt(2*N/(m-2)) где то так

Что вы, что вы! Business comes first!

ura · Сообщение **ura** » 31 май 2007, 10:24

aissp писал(а):Да тут Станислав поставил задачу прально:) N - этажность дома m - количество щариков... в последнем ответе n+m-2 дает минимальное количество бросков...

Меня терзают смутные сомнения, думаю что должен быть корень третьей степени при трех шарах, четвертой при четырех...Если это сводится к задаче минимизации площади(объема) в N мерном пространстве.

aissp · Сообщение **aissp** » 31 май 2007, 10:28

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

Дима · Сообщение **Дима** » 31 май 2007, 10:31

tma писал(а):
Дима писал(а):Ссылку эту видел По-моему, она не совсем не совсем соответствует задаче Пытаюсь разрезать карточки. Пока квадрата со стороной корень из 15-ти не получается Юрий, под широкими концами треугольника ты имел ввиду гипотенузу или бОльший катет ? И резать под прямым углом ?
Отмерить длину, равную корню из 15 получилось так:
египедский прямоугольный треугольник имеет стороны 3-4-5, на двух прямоугольниках имеем 3 и 5.
Положите первый прямоугольник на второй сверху и, придерживая один угол вместе, начинайте вращать второй прямоугольник против часовой стрелки на примерно 30 градусов до соприкосновения вершины первого со стороной второго. На просвет можно видеть, как сторона нижнего прямоугольника стала гипотенузой треугольника 3-4-5. Таким образом, отметили длину, равную 1. Т.е. прямоугольники размечены.
Дальше можно отметить длину, равную корню из 15, так. Гипотенуза прямоугольного треугольника со сторонами 1 и 1 =корню из 2.
Гипотенуза прямоугольного треугольника, построенного на катетах корень из 2 и 2, равна корню из 6.
Гипотенуза прямоугольного треугольника, построенного на катетах корень из 6 и 3, равна корню из 15.
Т.е. имеем корень из 15.

Да, спасибо большое, похоже это именно то, что нужно. До получения отрезка длины 1 я добрался (другим, правда, методом, 5-3=2, 3-2 = 1), а дальше не сообразил