Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
alexshch
1 / 1 / 0
Регистрация: 28.10.2015
Сообщений: 23
1

Шарики и небоскрёбы

20.11.2015, 23:49. Просмотров 2621. Ответов 3
Метки нет (Все метки)

В небоскребе 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
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2015, 23:49
Ответы с готовыми решениями:

Шарики
В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда...

Шарики
Помогите решить вот такую задачку: Несколько (N) шариков небольшого (радиуса r...

Шарики(Задача по олимпиадному программированию)
Решение(не идеально,я знаю): #include <iostream> #include <stdio.h> #include...

Посчитать шарики, которые будут уничтожены
Стас очень любит играть в игру "уничтожь шарики". Шарики в ней выставляются в...

Поменять местами черные и белые шарики (шашки)
*Имеется N лунок, в которых расставлены L черных и S белых шаров. Поменять...

3
anmartex
...
1711 / 1204 / 908
Регистрация: 12.02.2013
Сообщений: 1,978
21.11.2015, 12:08 2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
unsigned cnt(unsigned n) {
    return (n == 0) ? 0 : (1 + cnt(n / 2));
}
 
unsigned func(unsigned n) {
    return (n == 0) ? 0 : cnt(n - 1);
}
 
int main() {
    unsigned n;
    
    if (scanf("%u", &n) == 1) {
        printf("%u", func(n));
    }
    
    return 0;
}
0
_Ivana
3236 / 1867 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
21.11.2015, 17:38 3
Как в том анекдоте про Рабиновича - только не стеклянные шарики, а яйца Фаберже, и не 2 а сколько угодно
http://www.codewars.com/kata/54cb771c9b30e8b5250011d4
0
flash_back
8 / 8 / 20
Регистрация: 07.02.2016
Сообщений: 81
Завершенные тесты: 3
16.06.2016, 15:55 4
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
26
27
#include <iostream>
#include <cmath>
 
using namespace std;
 
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()
{
    int n;
    cin >> n;
    cout << get_num_throws(n);
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.06.2016, 15:55

Заставить шарики одновременно двигаться навстречу друг другу
Вот программа: #include &quot;graphics.h&quot; #include&lt;math.h&gt; int main() {...

Найти минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета
Написал код для одной задачи. Ответ выдает он вроде правильный. Но на сайте при...

Завод производит шарики для подшипников. Бракуются шарики, диаметр которых отличается от стандарта на 0,1 мм. Найти дисп
Завод производит шарики для подшипников. Бракуются шарики, диаметр которых...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru