Hợp Đồng

Tác giả:

Dạng bài

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

shiba mới kí một đơn hàng làm đồ ăn đóng gói. Do số lượng khách hàng yêu cầu quá lớn, cậu ấy quyết định sẽ đi tìm đến _minhduc để nhờ anh ấy thiết kế một dây chuyền sản xuất.

Dây chuyền sản xuất bao gồm một số lượng nhất định máy tự động làm đồ ăn. Bằng độ thiên tài của mình, _minhduc có thể làm ra một chiếc máy mà có thể làm được tất cả các công việc, từ sơ chế, làm nóng, hút chân không, đóng gói để bảo quản sản phẩm, chiếc máy đều có thể làm được hết. Tuy nhiên để làm ra một chiếc máy như vậy, _minhduc cần thời gian là \(1\) ngày. Bên cạnh đó, để một chiếc máy có thể làm ra một sản phẩm đồ ăn đóng gói đạt yêu cầu, cũng cần \(1\) ngày.

Ban đầu trên dây chuyền không có máy. _minhduc cần làm đủ số lượng máy, sau đó shiba mới có thể vận hành. Thời gian để hoàn thành hợp đồng bằng thời gian mà _minhduc lắp ráp máy cộng với thời gian những chiếc máy làm ra số lượng sản phẩm đạt yêu cầu. Lưu ý thời gian những chiếc máy làm ra sản phẩm được làm tròn lên (ví dụ: \(\left \lceil \frac{4}{2} \right \rceil = 2, \left \lceil \frac{5}{2} \right \rceil = 3\)).

shiba thắc mắc, thời gian tối thiểu cần thiết để cậu ấy hoàn thành hợp đồng là bao lâu, bởi hạn chót của hợp đồng càng ngắn thì shiba có thể kiếm được càng nhiều tiền.

Input

Dòng đầu chứa một số nguyên dương \(T\) \((T \leq 10^{5})\) - số lượng bộ test.
\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) \((n \leq 10^{12})\) - số lượng sản phẩm.

Output

Gồm \(T\) dòng, mỗi dòng chứa một số nguyên duy nhất là kết quả của mỗi bộ test.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(T, n \leq 100\).
Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

1
5

Output

Bình luận

-1

hint

#include <iostream>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

long long min_days_to_complete(long long n) {
    long long left = 1, right = n, min_days = LLONG_MAX;
    while (left <= right) {
        long long k = (left + right) / 2;
        long long days = k + (n + k - 1) / k;
        if (days < min_days) {
            min_days = days;
        }
        if (k < (n + k - 1) / k) {
            left = k + 1;
        } else {
            right = k - 1;
        }
    }
    return min_days;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        long long n;
        cin >> n;
        cout << min_days_to_complete(n) << "\n";
    }

    return 0;
}

4 bình luận nữa