Небоскреб и стеклянный шарик

@AGPro · Регистрация: 03.04.2016

Студворк — интернет-сервис помощи студентам

В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается. Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.

Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.

Формат входных данных
Программа получает на вход количество этажей в небоскребе.

Формат выходных данных
Требуется вывести наименьшее число бросков, при котором можно всегда решить задачу.

Примечание
Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.
Подсказки
1. Как следует действовать, если шарик был бы только один?
2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?
3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.

Sample Input 1: 4
Sample Output 1: 2
Sample Input 2: 5
Sample Output 2: 3

n/3 достаточно.
Бросаем первый с этажа номер n/3. Если разбился, то бросаем второй по очереди с 1 этажа, потом со 2, ... до n/3 пока не разобьется. Так найдем этаж.
Если первый шар не разбился. бросаем его с этажа 2n/3. Если тут разбился, то бросаем второй с этажа n/3+1, потом с n/3+2, ... пока не разобьется.
Если 1 шар при падении с 2n/3 не разбился, то бросаем его с 2n/3+1, потом с 2n/3+2, ... пока не разобьется.

Примерно так, надо закодить в с++

@avgoor · 07.04.2016, 02:20

Сообщение от Valeryn

Наверное что-то вроде этого?

Нет. У вас первый шар кидается с равными промежутками. При каждом броске интервал нужно сокращать на 1.

@vndtta · 07.04.2016, 10:39

Valeryn, в общем avgoor прав, потому как в условии шариков 2 или 1(п.п.1)
при произвольном количестве шариков задача усложняется раза в два, особенно для промежуточного случая, когда шариков хватает для метода дихотомии для нижней части этажей(нижней от отметки, где шарики не разбиваются при тесте), но не для верхней.

zer0mail · 07.04.2016, 11:17

Сколько бросков надо для 3 шариков и 1000 этажного дома? А для 4 шариков?

@AGPro · 07.04.2016, 11:39 **[ТС]**

Valeryn,

Сообщение от Valeryn

Что тут не так? Генерируем этаж, на котором шарик разбивается, в диапазоне 10-500+.
Указываем сколько шариков (их может быть 1 а может быть 100).

Вы рассмотрите попытки не с 10ого этажа , а с 1ого. Вот проверьте ваш код, неправильно работает. Мне известны только эти тесты.

1. тест: этажей - 4, ответ - 2
2. тест: этажей - 5, ответ - 3
3. тест: этажей - 6, ответ - 3
4. тест: этажей - 7, ответ - 3
5. тест: этажей - 8, ответ - 4
6. тест: этажей - 9, ответ - 4
7. тест: этажей - 10, ответ - 4
8. тест: этажей - 11, ответ - 4
9. тест: этажей - 12, ответ - 5
10. тест: этажей - 13, ответ - 5
11. тест: этажей - 14, ответ - 5
12. тест: этажей - 15, ответ - 5
13. тест: этажей - 16, ответ -5

@AGPro · 07.04.2016, 12:00 **[ТС]**

Решение:
Так как шариков всего два, то очевидно что, разбив первый, мы должны беречь второй и бросать его начиная с проверенного этажа поднимаясь по одному этажу вверх.

Представим схему бросаний в виде дерева: Верхний его уровень обозначает первое бросание. Если шарик разбивается, то уходим на левую ветвь, если нет, то продолжаем увеличивать этаж, уходя на правую ветвь. В итоге глубина узла этого дерева соответствует номеру испытания, которое он обозначает, а степень «правости» узла соответствует высоте этажа данного испытания. Цифра в узле обозначает этаж, на котором проводилось испытание.

https://www.cyberforum.ru/atta... 1460015297

Данная схема обозначает, что сначала бросили со 2 этажа, если шар разбился бросили с 1 этажа, если не разбился, то с 3.

Бросив шар с какого-то этажа N₁ мы либо разбиваем шарик, и идём начиная с первого вверх, либо не разбиваем шарик, и бросаем его тогда с какого-то другого этажа N₂, причём N₂>N₁

https://www.cyberforum.ru/atta... 1460015297

После испытания на N₂ этаже мы будем действовать так же, как и после испытания на N₁ этаже. (Потому что это единственно возможный вариант)

https://www.cyberforum.ru/atta... 1460015297

И так далее...
Т.к. длине алгоритма соответствует глубина дерева по соответствующим ветвям, то будем искать неизвестные N₁, N₂, ...
такие, чтобы все ветви имели одинаковую, и при том минимальную длину, при заданном количестве узлов (равном кол-ву этажей N_эт).

Длинна алгоритма очевидно тогда будет равна номеру первого этажа N₁.

Мы выразили все необходимые этажи через тот, на котором надо проводить первое испытание. Найдём и его.

https://www.cyberforum.ru/atta... 1460015297

Задача решена. Найден алгоритм, и все необходимые данные об этажах в зависимости от высоты небоскрёба.

Для 100 этажного дома N₁=13.65, округляя всегда в большую сторону, получим N₁=14.

https://www.cyberforum.ru/atta... 1460015297

Эксперты, правильно закодить сможете? В задаче надо дать ответ сколько минимум попыток надо сделать, а не номер этажа?

@AGPro · 07.04.2016, 12:29 **[ТС]**

N₁ Номер этажа с которого надо начинать бросать.
https://www.cyberforum.ru/atta... 1460017698

@avgoor · 07.04.2016, 13:15

Сообщение от zer0mail

Сколько бросков надо для 3? А для 4 шариков?

Задача решается похожим образом. Промежутки для первого шарика выбираются из суммы сумм натуральных чисел, когда разбили первый шарик решаем исходную задачу. Алгоритм нахождения необходимого числа бросков для N этажей и M шариков и сложности O(N*M) - предельно простой.

@AGPro · 07.04.2016, 14:01 **[ТС]**

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

https://www.cyberforum.ru/atta... 1460023179

Что-то типа этого?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <cmath>
 int main()
{
    int n_house, m, n;
    double n_1sbros;
        std::cin >> n_house;
n_1sbros = -((1-sqrt(8*n+1))*0.5);
    m = ceil(n_1sbros);
 //N(n) = m*n – (n-1)* n/2;
    std::cout << n;
return 0;
}

zer0mail · 07.04.2016, 15:06

Сообщение от avgoor

задача решается похожим образом. Промежутки для первого шарика выбираются из суммы сумм натуральных чисел, когда разбили первый шарик решаем исходную задачу. Алгоритм нахождения необходимого числа бросков для N этажей и M шариков и сложности O(N*M) - предельно простой.

Я задал конкретные числа и ответ меня интересует в в числах, а не в O(XXX).

@avgoor · 07.04.2016, 15:26

Сообщение от zer0mail

Сколько бросков надо для 3 шариков и 1000 этажного дома? А для 4 шариков?

1000 и 3 - 18
1000 и 4 - 11
Но могу ошибаться.

zer0mail · 07.04.2016, 16:09

Интересно, но у меня другие ответы:
3 19
4 13
Как минимум, один из нас ошибается.

С каких этажей бросается 1 шарик, пока не разобьется или не достигнет верхнего?

@avgoor · 07.04.2016, 17:01

Сообщение от zer0mail

С каких этажей бросается 1 шарик, пока не разобьется или не достигнет верхнего?

ХЗ. Я не смотрел.
К тому же после 30 поста нашел ошибку. Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int throwCount(int N, int M)
{
    std::vector<int> v(M);
    for (;;)
    {
        for (int i = M-1; i >=0 ; i--) {
            if (i == 0)
                v[0]++;
            else
                v[i] += v[i - 1];
            if (v[i] >= N - 1 && v[0] - i > 0)
                return v[0];
        }
    }
}

Добавлено через 2 минуты
Сейчас у меня тоже 19, 13.

zer0mail · 07.04.2016, 20:34

Для 3 шариков и 8 этажей сколько будет?

@AGPro · 08.04.2016, 00:34 **[ТС]**

Ребята, может вы рабочий код напишите для 2 шариков?

Добавлено через 1 час 16 минут
Проверьте свой код для 2 шариков этими тестами: ответ это количество испытаний.
1. тест: этажей - 4, ответ - 2
2. тест: этажей - 5, ответ - 3
3. тест: этажей - 6, ответ - 3
4. тест: этажей - 7, ответ - 3
5. тест: этажей - 8, ответ - 4
6. тест: этажей - 9, ответ - 4
7. тест: этажей - 10, ответ - 4
8. тест: этажей - 11, ответ - 4
9. тест: этажей - 12, ответ - 5
10. тест: этажей - 13, ответ - 5
11. тест: этажей - 14, ответ - 5
12. тест: этажей - 15, ответ - 5
13. тест: этажей - 16, ответ -5

@grizlik78 · 08.04.2016, 01:27

Два варианта:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
 
int get_num_throws(int level)
{
    if (level < 2)
        return 0;
    return ceil(0.5*sqrt(1+8*(level - 1))-0.5);
}
 
int get_num_throws2(int level)
{
    int num_throws = 0;
    long max_level = 1;
    while (max_level < level)
        max_level += ++num_throws;
    return num_throws;
}
 
int main()
{
    for (int level = 1; level < 108; ++level)
        std::cout << level <<": " << get_num_throws(level) 
            << " " << get_num_throws2(level) << std::endl;
}

@AGPro · 08.04.2016, 17:46 **[ТС]**

grizlik78, Отлично! Все ок!!! +Спасибо!

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89

	Небоскреб и стеклянный шарик 06.04.2016, 01:58. Показов 24517. Ответов 35 Метки нет (Все метки) В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается. Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер. Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу. Формат входных данных Программа получает на вход количество этажей в небоскребе. Формат выходных данных Требуется вывести наименьшее число бросков, при котором можно всегда решить задачу. Примечание Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа. Подсказки 1. Как следует действовать, если шарик был бы только один? 2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет? 3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a. Sample Input 1: 4 Sample Output 1: 2 Sample Input 2: 5 Sample Output 2: 3 n/3 достаточно. Бросаем первый с этажа номер n/3. Если разбился, то бросаем второй по очереди с 1 этажа, потом со 2, ... до n/3 пока не разобьется. Так найдем этаж. Если первый шар не разбился. бросаем его с этажа 2n/3. Если тут разбился, то бросаем второй с этажа n/3+1, потом с n/3+2, ... пока не разобьется. Если 1 шар при падении с 2n/3 не разбился, то бросаем его с 2n/3+1, потом с 2n/3+2, ... пока не разобьется. Примерно так, надо закодить в с++ 0

@vndtta 93 / 69 / 22 Регистрация: 17.10.2011 Сообщений: 235
	07.04.2016, 10:39
	Valeryn, в общем avgoor прав, потому как в условии шариков 2 или 1(п.п.1) при произвольном количестве шариков задача усложняется раза в два, особенно для промежуточного случая, когда шариков хватает для метода дихотомии для нижней части этажей(нижней от отметки, где шарики не разбиваются при тесте), но не для верхней. 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	07.04.2016, 11:17
	Сколько бросков надо для 3 шариков и 1000 этажного дома? А для 4 шариков? 0

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	07.04.2016, 12:00 [ТС]
	Решение: Так как шариков всего два, то очевидно что, разбив первый, мы должны беречь второй и бросать его начиная с проверенного этажа поднимаясь по одному этажу вверх. Представим схему бросаний в виде дерева: Верхний его уровень обозначает первое бросание. Если шарик разбивается, то уходим на левую ветвь, если нет, то продолжаем увеличивать этаж, уходя на правую ветвь. В итоге глубина узла этого дерева соответствует номеру испытания, которое он обозначает, а степень «правости» узла соответствует высоте этажа данного испытания. Цифра в узле обозначает этаж, на котором проводилось испытание. https://www.cyberforum.ru/atta... 1460015297 Данная схема обозначает, что сначала бросили со 2 этажа, если шар разбился бросили с 1 этажа, если не разбился, то с 3. Бросив шар с какого-то этажа N₁ мы либо разбиваем шарик, и идём начиная с первого вверх, либо не разбиваем шарик, и бросаем его тогда с какого-то другого этажа N₂, причём N₂>N₁ https://www.cyberforum.ru/atta... 1460015297 После испытания на N₂ этаже мы будем действовать так же, как и после испытания на N₁ этаже. (Потому что это единственно возможный вариант) https://www.cyberforum.ru/atta... 1460015297 И так далее... Т.к. длине алгоритма соответствует глубина дерева по соответствующим ветвям, то будем искать неизвестные N₁, N₂, ... такие, чтобы все ветви имели одинаковую, и при том минимальную длину, при заданном количестве узлов (равном кол-ву этажей N_эт). Длинна алгоритма очевидно тогда будет равна номеру первого этажа N₁. Мы выразили все необходимые этажи через тот, на котором надо проводить первое испытание. Найдём и его. https://www.cyberforum.ru/atta... 1460015297 Задача решена. Найден алгоритм, и все необходимые данные об этажах в зависимости от высоты небоскрёба. Для 100 этажного дома N₁=13.65, округляя всегда в большую сторону, получим N₁=14. https://www.cyberforum.ru/atta... 1460015297 Эксперты, правильно закодить сможете? В задаче надо дать ответ сколько минимум попыток надо сделать, а не номер этажа? Миниатюры Изображения 1

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	07.04.2016, 12:29 [ТС]
	N₁ Номер этажа с которого надо начинать бросать. https://www.cyberforum.ru/atta... 1460017698 Изображения 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	07.04.2016, 16:09
	Интересно, но у меня другие ответы: 3 19 4 13 Как минимум, один из нас ошибается. С каких этажей бросается 1 шарик, пока не разобьется или не достигнет верхнего? 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	07.04.2016, 20:34
	Для 3 шариков и 8 этажей сколько будет? 0

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	08.04.2016, 00:34 [ТС]
	Ребята, может вы рабочий код напишите для 2 шариков? Добавлено через 1 час 16 минут Проверьте свой код для 2 шариков этими тестами: ответ это количество испытаний. 1. тест: этажей - 4, ответ - 2 2. тест: этажей - 5, ответ - 3 3. тест: этажей - 6, ответ - 3 4. тест: этажей - 7, ответ - 3 5. тест: этажей - 8, ответ - 4 6. тест: этажей - 9, ответ - 4 7. тест: этажей - 10, ответ - 4 8. тест: этажей - 11, ответ - 4 9. тест: этажей - 12, ответ - 5 10. тест: этажей - 13, ответ - 5 11. тест: этажей - 14, ответ - 5 12. тест: этажей - 15, ответ - 5 13. тест: этажей - 16, ответ -5 0

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	08.04.2016, 17:46 [ТС]
	grizlik78, Отлично! Все ок!!! +Спасибо! 0