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à 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 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ụ: ). 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 - số lượng bộ test. dòng tiếp theo, mỗi dòng chứa một số nguyên dương - số lượng sản phẩm. Output Gồm 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 ( số điểm): . Subtask ( số điểm): không có ràng buộc gì thêm.

Solution

Gọi `x` là số máy cần sản xuất `(x in NN^**)`

`=>` Tổng số ngày cần dùng để sản xuất `n` sản phầm là: `x+ |~n/x~|` ngày

Do `x` nguyên dương `=>` `x+|~n/x~|=|~x+n/x~|`

Bài toán bây giờ trở thành: Tìm min của hàm số `f(x)=x+n/x` với `x` nguyên dương và `n` là một tham số cho trước trên đoạn `[1;+oo)`

Ta xét: `f^'(x)=1-n/x^2=0` `<=>` `x=sqrtn`

Ta có bảng xét dấu `f^'(x)` như sau:

\begin{array}{|c|cc|} \hline x&1&&\sqrt{n}&&+\infty \\\hline f'(x)&&-&0&+ \\\hline \end{array}

`=>` `f(x)` nghịch biến trên `(1;sqrtn)`, đồng biến trên `(sqrtn;+oo)` và đạt cực tiểu tại `x=sqrtn`

Từ đây, ta dễ thấy:

`+` Nếu `n` là số CP thì kết quả là `f(sqrtn)`

`+` Nếu `n` không là số CP thì kết quả là `min{f(|__sqrt(n)__|),f(|~sqrt(n)~|)}`

AC Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool isPerfectSquare(ll n) {
    ll s = sqrt(n);
    return s * s == n;
}
ll f(ll x, ll n) {
    return x + (n / x) + !(n % x == 0);
}
void solve(ll n) {
    if (isPerfectSquare(n)) cout << f(sqrt(n), n);
    else cout << min(f(sqrt(n), n), f(sqrt(n) + 1, n));
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin >> t;
    while (t--) {
        cin >> n;
        solve(n);
    }
    return 0;
}

`\color{red}{\text{@hoangduy67}}`

#include <bits/stdc++.h>
using namespace std;


int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    long long t, n, kq, k; cin >> t;
    while(t--){
        cin >> n;
        k = sqrt(n);
        if(n%k==0){
            k+=n/k;
        }else{
            k+=n/k+1;
        }
        cout << k <<'\n';
    }
}