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

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

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

В небоскребе 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++

#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++

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++

#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, Отлично! Все ок!!! +Спасибо!

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	07.04.2016, 02:20	21
	Сообщение от Valeryn Наверное что-то вроде этого? Нет. У вас первый шар кидается с равными промежутками. При каждом броске интервал нужно сокращать на 1. 0

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

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	07.04.2016, 12:00 [ТС]	25
	Решение: Так как шариков всего два, то очевидно что, разбив первый, мы должны беречь второй и бросать его начиная с проверенного этажа поднимаясь по одному этажу вверх. Представим схему бросаний в виде дерева: Верхний его уровень обозначает первое бросание. Если шарик разбивается, то уходим на левую ветвь, если нет, то продолжаем увеличивать этаж, уходя на правую ветвь. В итоге глубина узла этого дерева соответствует номеру испытания, которое он обозначает, а степень «правости» узла соответствует высоте этажа данного испытания. Цифра в узле обозначает этаж, на котором проводилось испытание. 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

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

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

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
		1
	Небоскреб и стеклянный шарик 06.04.2016, 01:58. Показов 21666. Ответов 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

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

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	07.04.2016, 11:39 [ТС]	24
	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 0

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

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	07.04.2016, 13:15	27
	Сообщение от zer0mail Сколько бросков надо для 3? А для 4 шариков? Задача решается похожим образом. Промежутки для первого шарика выбираются из суммы сумм натуральных чисел, когда разбили первый шарик решаем исходную задачу. Алгоритм нахождения необходимого числа бросков для N этажей и M шариков и сложности O(N*M) - предельно простой. 0

zer0mail 2664 / 2239 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	07.04.2016, 15:06	29
	Сообщение от avgoor задача решается похожим образом. Промежутки для первого шарика выбираются из суммы сумм натуральных чисел, когда разбили первый шарик решаем исходную задачу. Алгоритм нахождения необходимого числа бросков для N этажей и M шариков и сложности O(N*M) - предельно простой. Я задал конкретные числа и ответ меня интересует в в числах, а не в O(XXX). 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	07.04.2016, 15:26	30
	Сообщение от zer0mail Сколько бросков надо для 3 шариков и 1000 этажного дома? А для 4 шариков? 1000 и 3 - 18 1000 и 4 - 11 Но могу ошибаться. 0

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

@AGPro 9 / 9 / 2 Регистрация: 03.04.2016 Сообщений: 89
	08.04.2016, 00:34 [ТС]	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