Задачка про стаканы

beerukoffa

Имеется два крепких стакана и 100-этажный небоскреб. Требуется выяснить, с какого этажа (минимально) нужно сбросить стакан, чтобы он разбился (разбить можно не больше двух стаканов, естественно, потому что их всего два ). За какое количество сбрасываний можно гарантированно решить задачу? Например, если ответ "N", то нужный этаж всегда находится за N или менее сбрасываний.
П.С. Считаем, что стаканы не накапливают повреждения.

kasia74

за 50 сбрасываний

slo14

- легко
А вот над наименьшим - чуть подумать надо
UPDATE В смысле, над наименьшим таким очевидным способом.

slo14

Таким способом - 19.

kasia74

я, кажися, за 18 могу.

slo14

Да, конечно.
Не 19, а 18.
UPDATE Ой, нет

kasia74

какие мы умные!

kachokslava

ха! 15
UPD: возможно, 14. щас. подумаю
UPD: да, 14!

slo14

Кажется, догадываюсь - как.
Но считать ломает...

aqvamen

Сообщение удалил
таки 14

kachokslava

tramal

решение в студию! думать лень

aqvamen

гы, тоже было лень думать?

beerukoffa

Идея решения. Хотим найти за x ходов. Бросаем с этажа x, если разбивается поднимаемся по порядку с первого и все получается. Если не разбиваемся, поднимемся еще на x-1 (одна попытка уже израсходована) этажей. Далее аналогично.
x + (x-1) + ... + (x - (x-2 + (x - (x-1 = 100 <=> (x^2 + x) / 2 = 100 => x ~ 13.65

Dr_Jones

классно.

yukos1988

Ок
Хорошее решение!

aqvamen

Интереснее док-во неулучшаемости

Natka2394397

Доказательство, что за 13 нельзя:
Пусть сбросили 13 раз.
С(13,2) = 78 вариантов когда разбились оба.
С(13,1) = 13 вариантов когда разбился один.
С(13,0) = 1 вариант, когда оба остались целы.
ИТОГО: 92 случая мы способны отличить друг от друга. Это < 100.

UltraLoko

Какой Anonymous? Это я был! Я!

aqvamen

а тебя не спрашивали
весь подйоп испортил

aksirob

Методом деления пополам можно гарантированно сказать, что за 8.

kachokslava

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

aksirob

Не правильно понял условие.
Если разбиваем не больше 2-х стаканов, тогда предлагается такое решение:
n=1;
while(2стакана целы) {
Кидаем с (n+2)-го: if разбился then
{
Кидаем с n-го: if разбился then гарантированно n этаж,
if не разбился then Кидаем с (n+1)-го:
{
if разбился then гарантированно (n+1)-й этаж,
else гарантированно(n+2)-й этаж
}
}
}

tramal

счетчик увеличить забыл

aksirob

Эт точно
Оставить комментарий
Имя или ник:
Комментарий: