Tìm số bậc thang tối đa từ số gạch cho trước bằng C++

Mô tả bài toán

Cho N viên gạch. Bậc 1 dùng 2 viên, bậc 2 dùng 3 viên,... bậc i dùng i+1 viên. Tìm số bậc tối đa.

Ví dụ

N=40 → Output: 3 (giải thích: 2+3+4=9 ≤40, thêm bậc 4 cần 5 viên tổng 14... đến bậc 7 tổng 35, bậc 8 cần 9 >5 còn lại).

Giải thuật (Binary Search)

Tổng gạch cho k bậc = (k+1)(k+2)/2 - 1 = (k²+3k)/2. Tìm k lớn nhất thỏa (k²+3k)/2 ≤ N. Dùng binary search trên k ∈ [1, N/2].

Mã nguồn C++

#include <iostream>
using namespace std;

int findStairCount(int T) { // T = 2*N
    int low=1, high=T/2;
    while (low <= high) {
        int mid = (low+high)/2;
        long long val = 1LL*mid*(mid+1);
        if (val == T) return mid;
        if (mid>0 && val > T && 1LL*mid*(mid-1) <= T) return mid-1;
        if (val > T) high = mid-1;
        else low = mid+1;
    }
    return -1;
}

int main() {
    int N=60;
    int steps = findStairCount(2*N);
    if (steps != -1) steps--;
    cout << "Number of stair steps: " << steps;
    return 0;
}

Đầu ra

The number of stair steps that can be made is 9