Форум умных людей

у вас есть 2 идентичных деревяных шарика, и 100-этажный дом. Задание узнать с какого самого нижнего этажа шарикт разобьется,за минимальное количество кидков, при падении с более нижнего этажа шарики повреждения не получают.

классная задача, спс serebryanikk!
в первом приближении так:
3,6,9 и т.д. всего 33 но думаю это только начало, с удовольствием буду додумывать.. ::)

второй шарик контрольный? :)

4=25+3
5=20+4
6=17+5
7=15+6
8=13+7
9=12+8=20
10=10+9=19 - min (т.е. начинаем с 10 этажа и делаем максимум за 19 ходов) 8)
11=10+10=20

..а есть точный минимальный ответ?:-\

обьясни пожалуйста все эти записи гуманитарию - ?

хорош гуманитарий, я твою кажется только одну метмарфозу численную одолел. остальные не осилил! ::)
объясняю: бросаем с 4 этажа, если разбился - тогда со 2 другой шарик. если разбился - тогда это ответ, если нет - тогда с 3 и это ответ, если и с 3 нет - тогда ответом и был 4.
но нам невезет (впрочим, как всегда) и с 4 этажа шарик не разбивается. тогда идем с шагом 4. т.е. 4, 8, 12, 16 и т.д. и доходим до 100 этажа, а дальше так же как в примере с 4 этажем. получается 4, 8, 16, 24, 28, 32, ... 92, 96, 100 - всего 25 (или 24) хода. и теперь еще 3 хода от 96 к 100, чтобы, как ты вырвзился. сделать контрольный выстрел ;)
аналогично начиная с 5 этажа можно пройти за 20 (19) ходов до 100 (т.е. меньше чем в первом случае) и + еще 4 хода от 95 к 100 (т.е. больше чем в первом случае), но в сумме 20 (19)+4=23, что лучше чем 25(24)+3. так перебераем пока не выходим на ситуацию, когда, начиная с 11 этажа, сумма ходов от 1 до 100 и от верхней планки до 100 снова начинает увеличиваться. вывод - 10 этаж, 19 (18) ходов.  8)
но не уверен. что нельзя меньше. надо подумать.. ;)

Да... :(





  Кирпич упал на голову?И вы еще с нами! :)

18. есть варианты меньше?
в смысле? ???

неудачно пошутил

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

есть меньше 18, шарик может разбится и с первого этажа...Нужно знать наверняка.

спасибо подумаю

а ты если незаметил посмотри там сегодня задачи разделили на математику и логику, посмотри математику

а при чем тут 1-й этаж?
ну можно, конечно так: бросил один раз с 1 этажа. шарик разбился. ответ 1  8)

Да но нужно 100% вариант.

ну что значит 100%? если я стою на 90 этаже прийдя туда с шагом в 10 этажей, то я сделал к этому времени 9 шагов. дальше 2 варианта:
1) шарик не разбился на 90 этаже, тогда будет меньше, чем 18 бросков, т.к. имея 2 шарика я пройду оставшиеся 10 этажей максимум за 5 раз (наверняка меньше даже) и в сумме будет 9+5=14 шагов. 100%. но это если нам везет.
2) нам как всегда не везет, и шарик разбился на 90 этаже. тогда мне понадобится максимум 9 шагов, чтобы проверить последовательно все этажи с 81 по 89. Итого: 9+9=18 шагов. 100%

есть ответ меньше 17....

думаем  :-\

просто математический аукцион получается.  ;)
я умею за 16  8)

Я не скжу минималку ;) даже не старайся ;)
А если умеешь то валяй, я лишь даю подсказку на продолжение рагадывания вопроса.

меньше 16?
16 можно разными способами, вот один из них:
идем 7 шагов с длиной шага 10 этажей. стоим на 70 этаже. если на нем разбился (или раньше), тогда с 61 по 69 у нас есть 9 ходов, 7+9=16. если не разбился - идем 5 шагов с длиной шага 5. при этом если где-то до 95 этажа разбивается. то мы имеем меньше 16.. на 95 этаже расклад такой: 1) шарик разбился на 95, тогда с 91 по 94 имеем 4 шага, а всего 7+5+4=16. 2)шарик не разбился и тогда идем либо 98-96-97 (если разбился на 98), либо 98-99-100, т.е. всего имеем 7+5+3=15. но худший вариант в данном раскладе все-равно 16. :P
есть меньше? ???

есть. знаю за 14 8)

Валяй

ты знаешь меньше?

это становится выузыванием ответа, я больше подсказок говорить не буду(больше меньше),придумал вариант-говори. Хочешь замухлювать и вытащить из меня ответ получестным путем вот те :P
 ;)
Дальше буду говорьть только да/нет

да нет. вариант 14 могу рассказать, но я же не один в студии, мож кто еще подумать хочет.  ::)
а есть ли меньше обязательно нужно говорить, поскольку если это минимум то зачем мне заморачиваться, согласен? :-\

Ничего незнаю, кидай в личку там разберемся... ;)

не доверяете? >:(
а как тут кидать в личку, и еще давно хотел спросить у кого-нить как прикреплять файлы и вставлять текст между ними

В правом верхнем углу экрана будет написано
Здравствуйте, Smith
у Вас 1 сообщений, 1 новое.
Показать новые сообщения с Вашего последнего визита.
Показать новые ответы на Ваши сообщения.

или у каждого внизу под аватаркой

есть решение за 14 попыток:

№ броска 1 шарика	Этаж	Макс. кол-во бросков  2 шарика
1	14	13
2	27	12
3	39	11
4	50	10
5	60	9
6	69	8
7	77	7
8	84	6
9	90	5
10	95	4
11	99	3
12	100	0

Сначала кидаем первый шарик с этажей указанных в таблице, если он разбивается (например на 69), то начинаем кидать второй шарик с 61 этажа по 68

ок гуд

А Разор и не заметил, как написал доказательство того, что меньше, чем за 14, нельзя,

Граждане, можно меньше! Не с той стороны подход к задаче ищите!

моего решения Вы не видели, а я уже не помню)))) могу конечно вспомнить алгоритм, если нужно, но меньше 14 - не уверен, что можно.
кстати, Сэр, если ты читаешь, у тебя не сохранилось моя личка годовой давности?))))

Что за личка годовой давности? Это о чем?

Упс. Извиняюсь. Да, нельзя меньше, чем 14.
Вот толковое объяснение решения:

Если бы в наличии было всего одно яйцо, то пришлось бы последовательного сбрасывать его с первого этажа, потом со второго, и далее до сотого, но у нас их два, поэтому используем второе для минимизации количества тестов. Будем делить оставшееся количество этажей пополам, сначала сбросим яйцо с 50-го этажа, если разбилось, значит оставшееся яйцо надо будет последовательно сбрасывать с 1-го по 49й этаж, если не разбилось, то бросаем его снова, с 75-го этажа, и так далее. В худшем случае 50 тестов.
Это первое решение, которое пришло в голову так ищет информацию Rambler, тут коварный HR-менеджер предложит Вам улучшить своё решение, и не спешите спорить с ним на бутылку водки, что это решение и так самое лучшее.

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

Пусть X будет необходимое количество попыток. Таким образом, если одно яйцо разобьется, то оставшееся надо будет бросить X-1 раз. Если яйцо не разбилось, то на следующем этапе (если оно разобьется) на тесты с оставшимся яйцом останется X-2 попыток. Объясню на примере - Мы решили что оптимальное количество попыток всего 16, тогда бросаем одно яйцо с шестнадцатого этажа (уже одна израсходованная попытка), и если оно разбилось, то с помощью оставшегося проверяем 16-1=15 этажей. Если оно не разбилось, то у нас осталось в запасе 15 попыток, значит на следующем этапе нужно будет бросать яйцо (и еще одна попытка будет использована) с 16+15+1=32 этажа, так как если яйцо разобьется на 32м этаже, нам хватит 14 попыток чтобы проверить этажи с 17 по 31й.

Нам нужно найти, какое количество опытов будет оптимальным, это будет такое количество, при котором на заключительном этапе понадобится 0 экспериментов. Запишем это в виде последовательности:
(1+a) + (1+(a-1))+ (1+(a-2)) + ...+ (1+0) >= 100
Где 1+p это и будет то количество опытов, которое мы ищем, обозначим его X. Тогда X(X+1)/2 >=100 в нашем случае, надеюсь, Вы не забыли как решать квадратные уравнения?;) На случай, если забыли, ответ будет 14, соответственно одним яйцом (если оно не разбивается) будем проверять 14й, 27й, 39й, 50й, 60й, 69й, 77й, 84й, 90й, 95й, 99й, 100й этажи, если на одном из этапов яйцо разобьется, то проверим этажи, от максимального, где яйцо еще не билось, до того где оно разбилось.

Получаем результат - до 14 тестов.

Если бы в здании было 36 этажей, тогда X(X+1)/2>=36, решение было бы X=8, и проверить нужно будет 8, 15, 21, 26, 30, 33, 35, 36 этажи, пока яйцо не разобьется.

я как человек ленивый, прежде чем восстанавливать свое решение годовой давности прошу другого форумчанина проверить не сохранилось ли это самое решение у него в личных сообщениях, куда я ему его отправлял по его просьбе! :D

ну вот и разобрались  :)

Тут, видать, ошибка, т.к. на форуме я где-то 2-3 месяца. Это нереально, год назад меня тут не  было.:)

так я не тебе писАл, а ТС-у, т.е. серебряннику (памятнику, Сэру), его ветка же была ;)

Нет, условия этой задачи я услышал только сегодня.  :)

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

Без питань!