Здравствуйте, Кодт, Вы писали:
К>Ну если 50 этажей и объектов, то решение безо всякой динамики, лень в чистом виде: К>Берём с собой все 50 объектов и поднимаемся, роняя их на каждом этаже.
Извиняюсь, если не совсем точно сформулировал, но вот задача в исходной постановке:
На старости лет один профессор загорелся идеей
исследования на прочность транзисторов <<КД521(2)>>.
К сожалению, ему не удалось привлечь на помощь никого
из коллег, поэтому проводить измерения
придется самостоятельно. Но это не пугает профессора.
В шкафу профессор обнаружил $m$ транзисторов данной модели,
оставшихся со старых времен, и решил использовать их для
экспериментов.
После некоторых размышлений был выбран следующий способ
проведения измерений: профессор собирается, перемещаясь по
пожарной лестнице, сбрасывать транзисторы с различных
этажей. Таким образом он планирует определить, при падении
с какого минимального этажа транзистор разбивается.
При этом профессор уверен, что транзистор не может выдержать падение
с последнего этажа, однако падение с высоты человеческого роста
(то есть когда профессор находится на первом этаже) не причиняет
транзистору вреда.
Известно, что все транзисторы абсолютно одинаковые, и если
транзистор разбивается при падении с некоторого этажа,
то он разбивается и при падении со всех этажей с большим
номером.
Разбившиеся транзисторы снова использовать нельзя, а
если транзистор остался целым после падения, его можно
использовать повторно.
Для того, чтобы поднять оставшийся целым транзистор,
профессору надо спуститься на первый этаж. Оказавшись
на первом этаже, профессор может поднять все лежащие там транзисторы.
Годы профессора уже дают о себе знать, поэтому
он хочет минимизировать суммарное расстояние, которое ему придется
подниматься по лестнице.
Но, возраст дает и определенные преимущества ---
сняв очки, профессор может с любого этажа определить,
разбился транзистор или нет.
Изначально профессор находится на первом этаже, и
у него имеется $m$ транзисторов. В доме, в котором
живет профессор, $n$ этажей.
Найдите минимальное число этажей, которое профессору в худшем случае
придется подниматься вверх по лестнице во время проведения
экспериментов.
\InputFile
Во входном файле заданы два целых числа --- высота дома $n$
($2 \le n \le 50$) и количество транзисторов $m$ ($1 \le m \le 10$).
\OutputFile
В выходной файл выведите единственное число --- минимальное расстояние в
этажах, которое в худшем случае придется подниматься вверх по лестнице профессору
во время эксперимента.
\Example
5 2 -> 3
2 2 -> 0
В первом из приведенных примеров оптимальное поведение профессора следующее.
Сначала следует подняться на два этажа и бросить транзистор с третьего.
Если транзистор разобьется, то следует спуститься на второй
этаж и попытаться бросить транзистор оттуда --- если транзистор разбивается и при бросании
со второго этажа, то результат 2, иначе --- 3. Если же транзистор не разобьется при падении
с третьего этажа, то придется подняться на четвертый и бросить транзистор оттуда.
Если он разобьется, то результат 4, если нет --- 5. В худшем случае придется подняться
на три этажа.
Во втором примере ничего бросать не надо, результат исследования --- 2.
***
Re[2]: задачка про 100-этажное здание и шарики с водой
Про стекляшки и про бутылки.
Интересно дальнейшее направление мутаций
Что же касательно баянизмов — я уже говорил: если задача не проела мозг всем подряд (барометрия, монти-хилл, что там ещё такое злое есть), то пусть будет.
Пусть те, кто ещё не знает готового ответа, попробуют решить.
Не уверен, что подобной здесь не появлялось, но найти не смог...
Задача: есть 100-этажное здание и два шарика с водой. Вам необходимо наиболее оптимальным путем выяснить минимальный номер этажа при падении с которого шарик с водой лопается. Если шарик при падении не лопнул вы можете спуститься и подобрать его для повторного броска.
Ай синк со...
Re: задачка про 100-этажное здание и шарики с водой
Здравствуйте, geng, Вы писали:
G>Не уверен, что подобной здесь не появлялось, но найти не смог...
G>Задача: есть 100-этажное здание и два шарика с водой. Вам необходимо наиболее оптимальным путем выяснить минимальный номер этажа при падении с которого шарик с водой лопается. Если шарик при падении не лопнул вы можете спуститься и подобрать его для повторного броска.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, vadimcher, Вы писали:
G>>>Задача: есть 100-этажное здание и два шарика с водой.
V>>За последние пару лет было тут
.
К>Про стекляшки и про бутылки. К>Интересно дальнейшее направление мутаций
К>Что же касательно баянизмов — я уже говорил: если задача не проела мозг всем подряд (барометрия, монти-хилл, что там ещё такое злое есть), то пусть будет. К>Пусть те, кто ещё не знает готового ответа, попробуют решить.
Да я баяном ее и не обзывал. Старая добрая задачка... Просто до меня дали ссылку на совсем старый вариант, а задача в наиболее общем виде была здесь всего пару месяцев назад, вот и дал ссылку на обобщение.
А вот зайца кому, зайца-выбегайца?!
Re: задачка про 100-этажное здание и шарики с водой
Здравствуйте, geng, Вы писали:
G>Не уверен, что подобной здесь не появлялось, но найти не смог...
G>Задача: есть 100-этажное здание и два шарика с водой. Вам необходимо наиболее оптимальным путем выяснить минимальный номер этажа при падении с которого шарик с водой лопается. Если шарик при падении не лопнул вы можете спуститься и подобрать его для повторного броска.
Продолжая пьянку...
На школьной олимпиаде по информатике (ВКОШП) была модификация (там про профессора и транзисторы). Объекты разбиваются, не разбившиеся можно поднимать с земли. Цель — минимизировать число подъемов по лестнице (первоначально профессор находится на земле) что бы узнать номер этажа, начиная с которого бьется.
Ограничения — всего до 50. Максимум 50 этажей и 50 объектов для сбрасывания.
Наше (как и авторское) решение — ленивой динамикой. Но состояние (кортеж) было из 5 элементов. Впервые в жизни использовал пятимерный массив . Точнее даже 2, для ответа, и булевский, что были в этом состоянии.
Может можно как-то проще?
Re[2]: задачка про 100-этажное здание и шарики с водой
Здравствуйте, 67108864, Вы писали:
6>На школьной олимпиаде по информатике (ВКОШП) была модификация (там про профессора и транзисторы). Объекты разбиваются, не разбившиеся можно поднимать с земли. Цель — минимизировать число подъемов по лестнице (первоначально профессор находится на земле) что бы узнать номер этажа, начиная с которого бьется. 6>Ограничения — всего до 50. Максимум 50 этажей и 50 объектов для сбрасывания.
6>Наше (как и авторское) решение — ленивой динамикой. Но состояние (кортеж) было из 5 элементов. Впервые в жизни использовал пятимерный массив . Точнее даже 2, для ответа, и булевский, что были в этом состоянии.
Ну если 50 этажей и объектов, то решение безо всякой динамики, лень в чистом виде:
Берём с собой все 50 объектов и поднимаемся, роняя их на каждом этаже.
Необходимые условия:
— достаточная сила, чтоб тащить эту тяжесть
— острое зрение либо помощник внизу
Хотя даже и зрения не нужно: спустились вниз да посчитали, сколько не разбилось
Предполагается, что масса 50 объектов меньше массы человека, так что тащиться вверх с рюкзаком эффективнее, чем бегать вверх-вниз с единственным объектом.
... << RSDN@Home 1.2.0 alpha 4 rev. 1207>>
Перекуём баги на фичи!
Re[2]: задачка про 100-этажное здание и шарики с водой
Здравствуйте, geng, Вы писали:
G>Задача: есть 100-этажное здание и два шарика с водой. Вам необходимо наиболее оптимальным путем выяснить минимальный номер этажа при падении с которого шарик с водой лопается. Если шарик при падении не лопнул вы можете спуститься и подобрать его для повторного броска.
решение:
1й этаж — оба лопнули.
Re[2]: задачка про 100-этажное здание и шарики с водой
А что если действовать так:
1) Сбросили с первого этажа. Не лопнул, пункт 2.
2) Пришли на третий этаж. Сброили с третьего этажа. Лопнул — проверяем, лопнет ли с 2 этажа. Если лопнул на 2 этаже, значит минимальная выстоа — 2 этажа. Нет, значит минимальная высота — три этажа.
Не лопнул — к пункту 3.
3) Скидываем с пятого этажа...
В результате где-то 50 раз бегать прийдется, если 100 этажей
Re: задачка про 100-этажное здание и шарики с водой
Здравствуйте, geng, Вы писали:
G>Не уверен, что подобной здесь не появлялось, но найти не смог...
G>Задача: есть 100-этажное здание и два шарика с водой. Вам необходимо наиболее оптимальным путем выяснить минимальный номер этажа при падении с которого шарик с водой лопается. Если шарик при падении не лопнул вы можете спуститься и подобрать его для повторного броска.
Ха, а у нас на собеседованиях это одна из стандартных задач на "оценку мышления".
Re[3]: задачка про 100-этажное здание и шарики с водой
Здравствуйте, __kain, Вы писали:
__>А что если действовать так: __>1) Сбросили с первого этажа. Не лопнул, пункт 2. __>2) Пришли на третий этаж. Сброили с третьего этажа. Лопнул — проверяем, лопнет ли с 2 этажа. Если лопнул на 2 этаже, значит минимальная выстоа — 2 этажа. Нет, значит минимальная высота — три этажа.
__>Не лопнул — к пункту 3. __>3) Скидываем с пятого этажа...
__>В результате где-то 50 раз бегать прийдется, если 100 этажей
1) Сбросили с 14-го этажа. Не лопнул, пункт 2.
2) Сбросили с (14+13) = 27-го этажа. Не лопнул, пункт 3.
3) Сбросили с (27+12) = 39-го этажа. Ну скажем лопнул.
сбрасываем с 27+1,27+2,27+3... 38 пока не лопнет.
и того получаем 14ть попыток.
конечно это всё уже было но вот интересно тут откуда взялось число 14?
а если этажей будет скажем 200, то с какого начинать бегать? перебор никагда не приветствовался в советских школах.
Формула такая:
f = sqrt(2*N)
N — к-во етажей
f — первый етаж
Для 200 будет 20-й
Re[4]: задачка про 100-этажное здание и шарики с водой
M>1) Сбросили с 14-го этажа. Не лопнул, пункт 2. M>2) Сбросили с (14+13) = 27-го этажа. Не лопнул, пункт 3. M>3) Сбросили с (27+12) = 39-го этажа. Ну скажем лопнул.
M>сбрасываем с 27+1,27+2,27+3... 38 пока не лопнет. M>и того получаем 14ть попыток.
M>конечно это всё уже было но вот интересно тут откуда взялось число 14? M>а если этажей будет скажем 200, то с какого начинать бегать? перебор никагда не приветствовался в советских школах.
M>Формула такая: M> f = sqrt(2*N) M>N — к-во етажей M>f — первый етаж M>Для 200 будет 20-й
Только надо брать round(sqrt(2*N)), округлять к ближайшему числу вверх или вниз по обычным правилам, т.е. к ближайшему целому.
у меня выведена немного другая формула: первый этаж ceil( (sqrt (1+8*N) — 1) / 2 ), где ceil -- округление вверх. Так вот, на самом деле мы можем сначала заменить ceil(x) на round'(x+1/2), причем этот round' должен округлять 1/2 вниз (против обычных правил), получим round'(sqrt(2*N+1/4)), а затем можно заметить, что если мы уберем 1/4, то round' можно поменять на обычный round: единственная проблема, которая могла бы возникнуть, это то, что sqrt(2N+1/4)>k+1/2>sqrt(2N), но такого не может быть, т.к. тогда 2N>k^2+k>2N-1/4.
А вот зайца кому, зайца-выбегайца?!
Re[5]: задачка про 100-этажное здание и шарики с водой
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, madmat, Вы писали:
M>>1) Сбросили с 14-го этажа. Не лопнул, пункт 2. M>>2) Сбросили с (14+13) = 27-го этажа. Не лопнул, пункт 3. M>>3) Сбросили с (27+12) = 39-го этажа. Ну скажем лопнул.
M>>сбрасываем с 27+1,27+2,27+3... 38 пока не лопнет. M>>и того получаем 14ть попыток.
M>>конечно это всё уже было но вот интересно тут откуда взялось число 14? M>>а если этажей будет скажем 200, то с какого начинать бегать? перебор никагда не приветствовался в советских школах.
M>>Формула такая: M>> f = sqrt(2*N) M>>N — к-во етажей M>>f — первый етаж M>>Для 200 будет 20-й
V>Только надо брать round(sqrt(2*N)), округлять к ближайшему числу вверх или вниз по обычным правилам, т.е. к ближайшему целому.
V>Интересно, что вот тут
у меня выведена немного другая формула: первый этаж ceil( (sqrt (1+8*N) — 1) / 2 ), где ceil -- округление вверх. Так вот, на самом деле мы можем сначала заменить ceil(x) на round'(x+1/2), причем этот round' должен округлять 1/2 вниз (против обычных правил), получим round'(sqrt(2*N+1/4)), а затем можно заметить, что если мы уберем 1/4, то round' можно поменять на обычный round: единственная проблема, которая могла бы возникнуть, это то, что sqrt(2N+1/4)>k+1/2>sqrt(2N), но такого не может быть, т.к. тогда 2N>k^2+k>2N-1/4.
Это уж както сильно умно На самом деле тут кол-во этажей это интеграл от функции зависимости номера попытки и кол-ва этажей которые нужно проверить если шарик лопнет. в идеальном случае эта функция имеет вид равнобедренного прямоугольного треугольника в котором соответственно катет — кол-во этажей для первой попытки второй катет — кол-во попыток, катеты равны, а площадь и есть кол-во этажей. Формула f = sqrt(2*N)
это по сути нахождение катета равнобедренного прямоугольного треугольника по его площади.
Re[6]: задачка про 100-этажное здание и шарики с водой
Здравствуйте, madmat, Вы писали:
M>Это уж както сильно умно На самом деле тут кол-во этажей это интеграл от функции зависимости номера попытки и кол-ва этажей которые нужно проверить если шарик лопнет. в идеальном случае эта функция имеет вид равнобедренного прямоугольного треугольника в котором соответственно катет — кол-во этажей для первой попытки второй катет — кол-во попыток, катеты равны, а площадь и есть кол-во этажей. Формула f = sqrt(2*N) M>это по сути нахождение катета равнобедренного прямоугольного треугольника по его площади.
По-моему это ты сейчас как-то умно написал. Там все проще, ищется n такое, что n+(n-1)+...+1 = n(n+1)/2 >= N, где N -- количество этажей. Ясно, что искомое n где-то в районе sqrt(2N) (твой прямоугольный равнобедренный), но ты забываешь маленькую деталь, что решение должно быть целым числом, а потому возникает вопрос, в какую сторону округлять. Так вот, я всего лишь подсказал, что округлять надо к ближнему целому. Формула (sqrt(1+8N)-1)/2, например, тоже верная, но тут округляем строго вверх.
Перекуём баги на фичи!
На самом деле тут кол-во этажей это интеграл от функции зависимости номера попытки и кол-ва этажей которые нужно проверить если шарик лопнет. в идеальном случае эта функция имеет вид равнобедренного прямоугольного треугольника в котором соответственно катет — кол-во этажей для первой попытки второй катет — кол-во попыток, катеты равны, а площадь и есть кол-во этажей. Формула f = sqrt(2*N)