Максимальная высота лестницы

Question

Дано целое число A, представляющее квадратные блоки. Высота каждого квадратного блока равна 1. Задача состоит в том, чтобы создать лестницу максимальной высоты, используя эти блоки. Первая лестница потребует только один блок, вторая лестница потребует двух блоков и так далее. Найдите и верните максимальную высоту лестницы.

---

Ваша отправка не удалась для следующего ввода: A: 92761

Ваша функция вернула следующее: 65536
ожидаемое возвращаемое значение: 430

Approach:
We are interested in the number of steps and we know that each step Si uses exactly Bi number of bricks. We can represent this problem as an equation:
n * (n + 1) / 2 = T (For Natural number series starting from 1, 2, 3, 4, 5 …)
n * (n + 1) = 2 * T
n-1 will represent our final solution because our series in problem starts from 2, 3, 4, 5…

Now, we just have to solve this equation and for that we can exploit binary search to find the solution to this equation. Lower and Higher bounds of binary search are 1 and T.

КОД

public int solve(int A) {
        int l=1,h=A,T=2*A;
        while(l<=h)
        {
            int mid=l+(h-l)/2;
            if((mid*(mid+1))==T)  
                return mid;
            if((mid*(mid+1))>T && (mid!=0 && (mid*(mid-1))<=T) )
                return mid-1;
            if((mid*(mid+1))>T)
                h=mid-1;
            else
                l=mid+1;
        }
        return 0;
    }

Answer 1

Почему вы используете все эти формулы? Простой while() l oop должен добиться цели, в конце концов, это просто простая сумма Гаусса ..

public static int calculateStairs(int blocks) {
    int lastHeight = 0;
    int sum = 0;
    int currentHeight = 0; //number of bricks / level
    while (sum <= blocks) {
        lastHeight = currentHeight;
        currentHeight++;
        sum += currentHeight;
    }
    return lastHeight;
}

Answer 2

Чтобы расширить комментарий Мэтта Тиммерманса:

Вы знаете, что для n шагов вам нужно (n * (n + 1))/2 блоков. Вы хотите знать, если дано B блоков, сколько шагов вы можете создать.

Итак, у вас есть:

(n * (n + 1))/2 = B
(n^2 + n)/2 = B
n^2 + n = 2B
n^2 + n - 2B = 0

Это подозрительно похоже на то, для чего вы будете использовать quadrati c формула .

В этом случае a=1, b=1 и c=(-2B). Подставив числа в формулу:

n = ((-b) + sqrt(b^2 - 4*a*c))/(2*a)
  = (-1 + sqrt(1 - 4*1*(-2B)))/(2*a)
  = (-1 + sqrt(1 + 8B))/2
  = (sqrt(1 + 8B) - 1)/2

Итак, если у вас 5050 блоков, вы получите:

n = (sqrt(1 + 40400) - 1)/2
  = (sqrt(40401) - 1)/2
  = (201 - 1)/2
  = 100

Попробуйте с помощью квадратичного c калькулятора формул . Используйте 1 для значений a и b и замените c отрицательным числом, в два раза превышающим количество блоков, которые вы дали. Таким образом, в приведенном выше примере c будет -10100.

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

Answer 3

Так что это должно сделать работу, так как она также возвращает ожидаемое значение. Поправь меня, если я ошибаюсь.

public int solve(int blocks) {
    int current; //Create Variables
    for (int x = 0; x < Integer.MAX_VALUE; x++) { //Increment until return
      current = 0; //Set current to 0

        //Implementation of the Gauss sum
        for (int i = 1; i <= x; i++) { //Sum up [1,*current height*]
            current += i;
        } //Now we have the amount of blocks required for the current height

        //Now we check if the amount of blocks is bigger than
        // the wanted amount, and if so we return the last one
        if (current > blocks) {
            return x - 1;
        }
    }
    return current;
}